\textsc{Pull} and \textsc{PushPull} are PSPACE-complete

DOI10.1016/J.TCS.2016.03.012MaRDI QIDQ266272zbMATH OpenOpenAlexFDO

Authors Marcus Ritt, Luciana Buriol, André G. Pereira

Publication date 13 April 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.03.012

zbMATH Keywords

motion planningmoving-blocks problemsnondeterministic constraint logicPSPACE-completenessSokoban

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Artificial intelligence for robotics (68T40)

Recommendations

• Push-pull block puzzles are hard
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Pushing blocks is hard.
• scientific article; zbMATH DE number 2086639
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete

Cites work

• Assembling molecules in ATOMIX is hard
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1182933 (Why is no real title available?)
• Optimal Sokoban solving using pattern databases with specific domain knowledge
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Pushing blocks is hard.
• Relationships between nondeterministic and deterministic tape complexities
• SOKOBAN and other motion planning problems
• Sokoban: Enhancing general single-agent search methods using domain knowledge

Cited in

(13)

• Pushing blocks is hard.
• SOKOBAN and other motion planning problems
• PSPACE-completeness of Bloxorz and of games with 2-buttons
• Computational complexity of generalized Push Fight
• Computational complexity of motion planning of a robot through simple gadgets
• scientific article; zbMATH DE number 2002586 (Why is no real title available?)
• scientific article; zbMATH DE number 2086639 (Why is no real title available?)
• Quell
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete
• Push-pull block puzzles are hard
• \(1\times 1\) Rush Hour with fixed blocks is PSPACE-complete
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• Generalized Pete's Pike is PSPACE-complete

This page was built for publication: \textsc{Pull} and \textsc{PushPull} are PSPACE-complete

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