Generalized Pete's Pike is PSPACE-complete

DOI10.1016/J.TCS.2015.11.036zbMATH Open1333.68150OpenAlexW2187699282MaRDI QIDQ899314FDOQ899314

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

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

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)

Cites Work

• Assembling molecules in ATOMIX is hard
• Relationships between nondeterministic and deterministic tape complexities
• Title not available (Why is that?)
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• Fun with algorithms. 6th international conference, FUN 2012, Venice, Italy, June 4--6, 2012. Proceedings
• Computational Complexity of Two-Dimensional Platform Games
• Randolphs Robot Game is NP-hard!
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• Title not available (Why is that?)
• \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)