\textsc{Snowman} is PSPACE-complete

DOI10.1016/J.TCS.2017.03.011MaRDI QIDQ526872zbMATH OpenOpenAlexFDO

Authors Ziwen Liu, Chao Yang, Weihua He

Publication date 15 May 2017

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

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

zbMATH Keywords

combinatorial puzzlescomputational complexitynondeterministic constraint logicPSPACE-completeSokoban

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorial games (91A46)

Recommendations

• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• scientific article; zbMATH DE number 2086639
• PSPACE-completeness of Bloxorz and of games with 2-buttons
• SOKOBAN and other motion planning problems

Cites work

• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard
• Generalized Pete's Pike is PSPACE-complete
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 2002586 (Why is no real title available?)
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The Complexity of Snake

Cited in

(11)

• Lemmings is PSPACE-complete
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• PSPACE-completeness of Bloxorz and of games with 2-buttons
• scientific article; zbMATH DE number 2086639 (Why is no real title available?)
• Fixed-parameter algorithms for graph constraint logic
• Fixed-parameter algorithms for graph constraint logic
• On the complexity of motion planning problem of a forklift
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• On the computational complexity of pushing machine
• Friends-and-strangers is \textsf{PSPACE}-complete
• Generalized Pete's Pike is PSPACE-complete

This page was built for publication: \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete

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