Buchumschlag

BusOut is NP-complete

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ishibashi, Takehiro, Yoshinaka, Ryo, Shinohara, Ayumi
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
von: Dumitru, Radu Cosmin, et al.
Veröffentlicht: (2026)

StrNim: a variant of Nim played on strings
von: Mizuno, Shota, et al.
Veröffentlicht: (2025)

Misère Greedy Nim and Misère Bounded Greedy Nim
von: Omiya, Nanako, et al.
Veröffentlicht: (2025)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
von: Asadi, Ali, et al.
Veröffentlicht: (2024)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
von: Binnendyk, Eric
Veröffentlicht: (2025)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
von: Pfaue, Femke
Veröffentlicht: (2024)

P=NP
von: Deng, Zikang
Veröffentlicht: (2024)

Wataridori is NP-Complete
von: Ruangwises, Suthee
Veröffentlicht: (2026)

P vs. NP
von: Uribe, Daniel
Veröffentlicht: (2016)

On P Versus NP
von: Gordeev, Lev
Veröffentlicht: (2020)

Nondango is NP-Complete
von: Ruangwises, Suthee
Veröffentlicht: (2023)

The n-vehicle exploration problem is NP-complete
von: Cui, Jinchuan, et al.
Veröffentlicht: (2023)

Evolomino is NP-complete
von: Nikolaev, Andrei V.
Veröffentlicht: (2025)

On $NP \cap coNP$ proof complexity generators
von: Krajicek, Jan
Veröffentlicht: (2025)

Proofs of NP = coNP = PSPACE: Current upgrade
von: Gordeev, Lev, et al.
Veröffentlicht: (2023)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
von: DeJesse, Nicholas, et al.
Veröffentlicht: (2025)

Communication Complexity is NP-hard
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

On Kernelization with Access to NP-Oracles
von: Molter, Hendrik, et al.
Veröffentlicht: (2025)

A Critique of Deng's "P=NP"
von: Humphreys, Isabel, et al.
Veröffentlicht: (2025)

NP-Completeness of Neighborhood Balanced Colorings
von: Asaeedi, Saeed
Veröffentlicht: (2024)

The 2-Attractor Problem is NP-Complete
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
von: Zhan, Junpeng
Veröffentlicht: (2023)

NP-Completeness of Multicast Beamforming in Wireless Communication
von: Shrestha, Sagar
Veröffentlicht: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
von: Johnson, Matthew, et al.
Veröffentlicht: (2022)

Some conditions implying if P=NP then P=PSPACE
von: Rodriguez, Ismael
Veröffentlicht: (2026)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
von: Mitosek, Piotr
Veröffentlicht: (2024)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
von: Romão, Leonardo Gasparini, et al.
Veröffentlicht: (2025)

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
von: Meng, Boning, et al.
Veröffentlicht: (2025)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
von: Martinsson, Björn
Veröffentlicht: (2024)

Limits of structures and Total NP Search Problems
von: Ježil, Ondřej
Veröffentlicht: (2023)

The 7 faces of quantum NP
von: Gharibian, Sevag
Veröffentlicht: (2023)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
von: Digulescu, Mircea-Adrian
Veröffentlicht: (2026)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
von: Çivril, Ali
Veröffentlicht: (2021)

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
von: Dingel, David, et al.
Veröffentlicht: (2024)

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
von: Baraskar, Omkar, et al.
Veröffentlicht: (2024)

Mim-Width is paraNP-complete
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

King Chasing Problem in Chinese Chess is NP-hard
von: Li, Chao, et al.
Veröffentlicht: (2026)

NP-hardness of SVP in Euclidean Space
von: Wan, Daqing
Veröffentlicht: (2026)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
von: Dorfer, Joseph
Veröffentlicht: (2026)