Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911662278180864 |
|---|---|
| author | MIT Hardness Group Brunner, Josh Chung, Lily Demaine, Erik D. Diomidova, Jenny Hendrickson, Della Lynch, Jayson |
| author_facet | MIT Hardness Group Brunner, Josh Chung, Lily Demaine, Erik D. Diomidova, Jenny Hendrickson, Della Lynch, Jayson |
| contents | We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (immovable) walls from a 2022 result. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP-hard in 2000, but its final complexity remained open for 25 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also introduce a new connection between the motion-planning-through-gadgets framework (with an agent) and the Graph Orientation Reconfiguration Problem (with no agent), including Nondeterministic Constraint Logic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19759 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete MIT Hardness Group Brunner, Josh Chung, Lily Demaine, Erik D. Diomidova, Jenny Hendrickson, Della Lynch, Jayson Computational Complexity We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (immovable) walls from a 2022 result. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP-hard in 2000, but its final complexity remained open for 25 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also introduce a new connection between the motion-planning-through-gadgets framework (with an agent) and the Graph Orientation Reconfiguration Problem (with no agent), including Nondeterministic Constraint Logic. |
| title | Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2508.19759 |