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

DOI10.4230/LIPICS.FUN.2021.3zbMath1515.68148MaRDI QIDQ6487567

Yenhenii Diomidov, Erik D. Demaine, Dylan Hendrickson, Jayson Lynch, Jeffrey Bosboom, Joshua Ani

Publication date: 7 February 2023

zbMATH Keywords

motion planninggadgetshardness of games

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Related Items (5)

Defying gravity and gadget numerosity: the complexity of the Hanano puzzle ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Traversability, reconfiguration, and reachability in the gadget framework ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets

This page was built for publication: Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets