On the computational complexity of pushing machine

DOI10.1007/978-3-032-00281-5_25MaRDI QIDQ6866952zbMATH OpenFDO

Authors Chao Yang

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-3-032-00281-5_25

zbMATH Keywords

\textsf{PSPACE}-completecombinatorial puzzlescomputational complexityoriented subway shufflepushing machine

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Applications of game theory (91A80)

Cites work

• \(1\times 1\) Rush Hour with fixed blocks is PSPACE-complete
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• SOKOBAN and other motion planning problems
• Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets

This page was built for publication: On the computational complexity of pushing machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866952)