Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets
From MaRDI portal
Publication:6487567
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
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
