Copertina

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Ani, Hayashi, Chung, Lily, Demaine, Erik D., Diomidova, Jenny, Hendrickson, Della, Lynch, Jayson
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
di: MIT Gadgets Group, et al.
Pubblicazione: (2020)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

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

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
di: DeStefano, Zachary, et al.
Pubblicazione: (2025)

Tetris is Hard with Just One Piece Type
di: MIT Hardness Group, et al.
Pubblicazione: (2026)

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
di: MIT Hardness Group, et al.
Pubblicazione: (2026)

Folding One Polyhedral Metric Graph into Another
di: Chung, Lily, et al.
Pubblicazione: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

Undecidability of Tiling with a Tromino
di: ULB CompGeom Group, et al.
Pubblicazione: (2025)

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

All Polyhedral Manifolds are Connected by a 2-Step Refolding
di: Chung, Lily, et al.
Pubblicazione: (2024)

All Polyhedral Manifolds are Connected by a 2-Step Refolding
di: Chung, Lily, et al.
Pubblicazione: (2025)

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

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

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

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

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

Lifting for Arbitrary Gadgets
di: Iyer, Siddharth
Pubblicazione: (2025)

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

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

Tetris with Few Piece Types
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

Col is PSPACE-complete on Triangular Grids
di: Burke, Kyle, et al.
Pubblicazione: (2025)

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

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

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
di: Hirahara, Shuichi, et al.
Pubblicazione: (2023)

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

The Separation of $NP$ and $PSPACE$
di: Lin, Tianrong
Pubblicazione: (2021)

Distributed Quantum Advantage in Locally Checkable Labeling Problems
di: Balliu, Alkida, et al.
Pubblicazione: (2025)

Graph Threading with Turn Costs
di: Demaine, Erik D., 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)

Tight Lower Bounds for Block-Structured Integer Programs
di: Hunkenschröder, Christoph, et al.
Pubblicazione: (2024)

A Simple Proof that Ricochet Robots is PSPACE-Complete
di: Balanza-Martinez, Jose, et al.
Pubblicazione: (2024)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
di: Burke, Kyle, et al.
Pubblicazione: (2025)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
di: Grüne, Christoph, et al.
Pubblicazione: (2026)

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

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
di: Nalli, Sai Soumya, et al.
Pubblicazione: (2026)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

SAT, Gadgets, Max2XOR, and Quantum Annealers
di: Ansótegui, Carlos, et al.
Pubblicazione: (2024)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
di: Bodirsky, Manuel, et al.
Pubblicazione: (2024)