Generalized Pete's Pike is PSPACE-complete

DOI10.1016/J.TCS.2015.11.036MaRDI QIDQ899314zbMATH OpenOpenAlexFDO

Authors Bernd Meyer

Publication date 28 December 2015

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

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

zbMATH Keywords

PSPACE-completenesslogic puzzlesolitaire gamesUFO puzzle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving topology, set theory, or logic (91A44)

Recommendations

• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Computational complexity of generalized Push Fight
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete
• Computational complexity of two-dimensional platform games
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete

Cites work

• scientific article; zbMATH DE number 2002586 (Why is no real title available?)
• scientific article; zbMATH DE number 1882054 (Why is no real title available?)
• Assembling molecules in ATOMIX is hard
• Computational complexity of two-dimensional platform games
• Fun with algorithms. 6th international conference, FUN 2012, Venice, Italy, June 4--6, 2012. Proceedings
• Games, puzzles, and computation
• Randolphs Robot Game is NP-hard!
• Relationships between nondeterministic and deterministic tape complexities
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants

Cited in

(2)

• On the complexity of motion planning problem of a forklift
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete

This page was built for publication: Generalized Pete's Pike is PSPACE-complete

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