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

DOI10.1016/J.TCS.2016.03.012zbMath1338.68088OpenAlexW2296061337MaRDI QIDQ266272

Marcus Ritt, Luciana S. Buriol, André G. C. 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 planningSokobanPSPACE-completenessmoving-blocks problemsnondeterministic constraint logic

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete

Cites Work

• Optimal Sokoban solving using pattern databases with specific domain knowledge
• Pushing blocks is hard.
• SOKOBAN and other motion planning problems
• Assembling molecules in ATOMIX is hard
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Sokoban: Enhancing general single-agent search methods using domain knowledge
• Unnamed Item
• Unnamed Item

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