Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
MIT Gadgets Group, Jeffrey Bosboom, Erik D. Demaine +4
An open-close door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "opening" and "closing" tunnels set the gadget's state to op…
cs.CC2024
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
Hayashi Ani, Lily Chung, Erik D. Demaine +3
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…