Copertina

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	DeStefano, Zachary, Liang, Bufang
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Computational Geometry
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
di: Ani, Hayashi, et al.
Pubblicazione: (2024)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
di: MIT Hardness Group, et al.
Pubblicazione: (2025)

Atropos-k is PSPACE-complete
di: Yang, Chao, et al.
Pubblicazione: (2024)

Verifying Quantized Graph Neural Networks is PSPACE-complete
di: Sälzer, Marco, et al.
Pubblicazione: (2025)

Maker-Maker games of rank 4 are PSPACE-complete
di: Galliot, Florian, et al.
Pubblicazione: (2025)

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
di: Galliot, Florian
Pubblicazione: (2025)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
di: Meijer, Lucas, et al.
Pubblicazione: (2025)

The Parameterized Complexity of Geometric 1-Planarity
di: Firbas, Alexander
Pubblicazione: (2026)

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

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

A conservative Turing complete $S^4$ flow
di: Suárez-Serrato, Pablo
Pubblicazione: (2023)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
di: Silva, Lucas de Oliveira, et al.
Pubblicazione: (2025)

Battle Sheep is PSPACE-complete
di: Burke, Kyle, et al.
Pubblicazione: (2025)

Some conditions implying if P=NP then P=PSPACE
di: Rodriguez, Ismael
Pubblicazione: (2026)

On Saxe's theorems about the complexity of the Distance Geometry Problem
di: Kupperschmitt, Maël, et al.
Pubblicazione: (2025)

Minimum Selective Subset on Some Graph Classes
di: Manna, Bubai
Pubblicazione: (2025)

Counting Triangulations of Fixed Cardinal Degrees
di: Chambers, Erin, et al.
Pubblicazione: (2025)

Query-Efficient Fixpoints of $\ell_p$-Contractions
di: Haslebacher, Sebastian, et al.
Pubblicazione: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
di: Gibor, Daniel
Pubblicazione: (2025)

Realizing Metric Spaces with Convex Obstacles
di: Kisfaludi-Bak, Sándor, et al.
Pubblicazione: (2025)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
di: Manna, Bubai
Pubblicazione: (2025)

On the complexity of embedding in graph products
di: Biedl, Therese, et al.
Pubblicazione: (2023)

Geometric Bipartite Matching is in NC
di: Bhore, Sujoy, et al.
Pubblicazione: (2024)

Complexity of 2D Snake Cube Puzzles
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

Constrained Boundary Labeling
di: Depian, Thomas, et al.
Pubblicazione: (2024)

On the hardness of finding normal surfaces
di: Burton, Benjamin A., et al.
Pubblicazione: (2019)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
di: Boomari, Hossein, et al.
Pubblicazione: (2018)

Pathways to Tractability for Geometric Thickness
di: Depian, Thomas, et al.
Pubblicazione: (2024)

The Complexity of Drawing Graphs on Few Lines and Few Planes
di: Chaplick, Steven, et al.
Pubblicazione: (2016)

On the complexity of covering points by guillotine cuts
di: Garijo, Delia, et al.
Pubblicazione: (2026)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

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

Paintbucket on graphs is PSPACE-complete
di: Saunders, Ethan J., et al.
Pubblicazione: (2024)

Proofs of NP = coNP = PSPACE: Current upgrade
di: Gordeev, Lev, et al.
Pubblicazione: (2023)

Turing complete Navier-Stokes steady states via cosymplectic geometry
di: Dyhr, Søren, et al.
Pubblicazione: (2025)

Undecidability of Translational Tiling with Three Tiles
di: Yang, Chan, et al.
Pubblicazione: (2024)

Translational Aperiodic Sets of 7 Polyominoes
di: Yang, Chao, et al.
Pubblicazione: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
di: Chavrimootoo, Michael C., et al.
Pubblicazione: (2026)

Existence and nonexistence of commutativity gadgets for entangled CSPs
di: Culf, Eric, et al.
Pubblicazione: (2025)

The Borsuk number of a graph
di: Cáceres, José, et al.
Pubblicazione: (2026)