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

DOI10.1016/j.tcs.2017.03.011zbMath1370.68129OpenAlexW2595427428MaRDI QIDQ526872

Chao Yang, Ziwen Liu, Wei-Hua 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

computational complexitySokobanPSPACE-completenondeterministic constraint logiccombinatorial puzzles

Mathematics Subject Classification ID

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

Related Items (3)

Fixed-parameter algorithms for graph constraint logic ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• Generalized Pete's Pike is PSPACE-complete
• The \((n^ 2-1)\)-puzzle and related relocation problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
• The Complexity of Snake
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants

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