Lemmings is PSPACE-complete

DOI10.1016/j.tcs.2015.01.055zbMath1327.68121OpenAlexW2034395812MaRDI QIDQ2347006

Giovanni Viglietta

Publication date: 26 May 2015

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

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

zbMATH Keywords

puzzlecomputational complexityPSPACEAPXLemmingsvideo game

Mathematics Subject Classification ID

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

Related Items (6)

The complexity of speedrunning video games ⋮ The Computational Complexity of Portal and Other 3D Video Games ⋮ Unnamed Item ⋮ The computational complexity of Angry Birds ⋮ Lemmings is PSPACE-complete ⋮ Classic Nintendo games are (computationally) hard

Cites Work

• Gaming is a hard job, but someone has to do it!
• Lemmings is PSPACE-complete
• Computational Complexity of Two-Dimensional Platform Games
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lemmings is PSPACE-complete