Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912171534843904 |
|---|---|
| author | Ani, Hayashi Chung, Lily Demaine, Erik D. Diomidova, Jenny Hendrickson, Della Lynch, Jayson |
| author_facet | Ani, Hayashi Chung, Lily Demaine, Erik D. Diomidova, Jenny Hendrickson, Della Lynch, Jayson |
| contents | We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (introduced in 1999). The proof also extends to Push-$k$ for any $k \ge 2$. We also prove PSPACE-completeness of two versions of the recently studied block-moving puzzle game with gravity, Block Dude - a video game dating back to 1994 - featuring either liftable blocks or pushable blocks. Two of our reductions are built on a new framework for "checkable" gadgets, extending the motion-planning-through-gadgets framework to support gadgets that can be misused, provided those misuses can be detected later. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20079 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude Ani, Hayashi Chung, Lily Demaine, Erik D. Diomidova, Jenny Hendrickson, Della Lynch, Jayson Computational Complexity We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (introduced in 1999). The proof also extends to Push-$k$ for any $k \ge 2$. We also prove PSPACE-completeness of two versions of the recently studied block-moving puzzle game with gravity, Block Dude - a video game dating back to 1994 - featuring either liftable blocks or pushable blocks. Two of our reductions are built on a new framework for "checkable" gadgets, extending the motion-planning-through-gadgets framework to support gadgets that can be misused, provided those misuses can be detected later. |
| title | Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2412.20079 |