Cover Image

The n-vehicle exploration problem is NP-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cui, Jinchuan, Li, Xiaoya
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity 68Q17, 90C27
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
by: Emmerich, Michael T. M., et al.
Published: (2026)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
by: Emmerich, Michael T. M., et al.
Published: (2026)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
by: Ye, Yuhan
Published: (2026)

Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems
by: Hartung, Tobias, et al.
Published: (2025)

Harnessing Inferior Solutions For Superior Outcomes: Obtaining Robust Solutions From Quantum Algorithms
by: Halffmann, Pascal, et al.
Published: (2024)

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
by: Cui, Jinchuan, et al.
Published: (2022)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
by: Goerigk, Marc, et al.
Published: (2026)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems
by: Duchnowski, Alex, et al.
Published: (2025)

Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
by: Pak, Igor, et al.
Published: (2025)

Vanishing of Schubert coefficients in probabilistic polynomial time
by: Pak, Igor, et al.
Published: (2025)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
by: Lobe, Elisabeth, et al.
Published: (2021)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
by: Meir, Or
Published: (2023)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Stiefel optimization is NP-hard
by: Lai, Zehua, et al.
Published: (2025)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis
by: Petrov, Petar P.
Published: (2022)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
by: Emmerich, Michael T. M., et al.
Published: (2026)

Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model
by: Lakshmanan, K
Published: (2023)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Blended Conditional Gradients: the unconditioning of conditional gradients
by: Braun, Gábor, et al.
Published: (2018)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)