Walking through doors is hard, even without staircases: Proving PSPACE-hardness via planar assemblies of door gadgets

Walking through doors is hard, even without staircases: Proving PSPACE-hardness via planar assemblies of door gadgets

A door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the “open” and “close” tunnel sets the gadget's state to open and closed, respectively, while the “traverse” tunnel can be traversed if and only if the door is in the open state. We prove tha...

Full description

Bibliographic Details
Main Authors: Ani, Joshua, Bosboom, Jeffrey William, Demaine, Erik D, Diomidov, Y, Hendrickson, Dylan H., Lynch, Jayson
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Dagstuhl Publishing 2020
Online Access:https://hdl.handle.net/1721.1/128836

Internet

https://hdl.handle.net/1721.1/128836

Similar Items