PSPACE-Completeness of Bloxorz and of Games with 2-Buttons

DOI10.1007/978-3-319-18173-8_30zbMath1459.68080arXiv1411.5951OpenAlexW1490609806WikidataQ59567446 ScholiaQ59567446MaRDI QIDQ2947039

Tom C. van der Zanden, Hans L. Bodlaender

Publication date: 21 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.5951

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Related Items (7)

Games, Puzzles and Treewidth ⋮ The Computational Complexity of Portal and Other 3D Video Games ⋮ PSPACE-Completeness of Bloxorz and of Games with 2-Buttons ⋮ Fixed-parameter algorithms for graph constraint logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The computational complexity of Angry Birds

Cites Work

• Unnamed Item
• Gaming is a hard job, but someone has to do it!
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• PSPACE-Completeness of Bloxorz and of Games with 2-Buttons
• Computational Complexity of Two-Dimensional Platform Games
• Undirected connectivity in log-space

This page was built for publication: PSPACE-Completeness of Bloxorz and of Games with 2-Buttons