Buchumschlag

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	MIT Hardness Group, Brunner, Josh, Chung, Lily, Demaine, Erik D., Diomidova, Jenny, Hendrickson, Della, Lynch, Jayson
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

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

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

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

Tetris is Hard with Just One Piece Type
von: MIT Hardness Group, et al.
Veröffentlicht: (2026)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

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

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
von: MIT Hardness Group, et al.
Veröffentlicht: (2026)

Tetris with Few Piece Types
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Complexity of 2D Snake Cube Puzzles
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

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

Undecidability of Tiling with a Tromino
von: ULB CompGeom Group, et al.
Veröffentlicht: (2025)

Folding One Polyhedral Metric Graph into Another
von: Chung, Lily, et al.
Veröffentlicht: (2024)

All Polyhedral Manifolds are Connected by a 2-Step Refolding
von: Chung, Lily, et al.
Veröffentlicht: (2024)

All Polyhedral Manifolds are Connected by a 2-Step Refolding
von: Chung, Lily, et al.
Veröffentlicht: (2025)

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

A Simple Proof that Ricochet Robots is PSPACE-Complete
von: Balanza-Martinez, Jose, et al.
Veröffentlicht: (2024)

Quoridor is PSPACE-Complete
von: Drop, Marius, et al.
Veröffentlicht: (2026)

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

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

Atropos-k is PSPACE-complete
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints
von: NASA Space Robots Team, et al.
Veröffentlicht: (2024)

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

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2023)

The Separation of $NP$ and $PSPACE$
von: Lin, Tianrong
Veröffentlicht: (2021)

Distributed Quantum Advantage in Locally Checkable Labeling Problems
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

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

Maker-Maker games of rank 4 are PSPACE-complete
von: Galliot, Florian, et al.
Veröffentlicht: (2025)

Graph Threading with Turn Costs
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
von: Galliot, Florian
Veröffentlicht: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Verifying Quantized Graph Neural Networks is PSPACE-complete
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)

Friends-and-strangers is PSPACE-complete
von: Yang, Chao, et al.
Veröffentlicht: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Battle Sheep is PSPACE-complete
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

Hive is PSPACE-Hard
von: Andel, Daniël, et al.
Veröffentlicht: (2025)

Paintbucket on graphs is PSPACE-complete
von: Saunders, Ethan J., et al.
Veröffentlicht: (2024)

Col is PSPACE-complete on Triangular Grids
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Improving the Leading Constant of Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2024)