Lemmings is PSPACE-complete

DOI10.1016/J.TCS.2015.01.055MaRDI QIDQ2347006zbMATH OpenOpenAlexFDO

Authors G. 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

APXcomputational complexityLemmingsPSPACEpuzzlevideo game

Mathematics Subject Classification ID

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

Recommendations

• Computational complexity of two-dimensional platform games
• Gaming is a hard job, but someone has to do it!
• PSPACE-completeness of Bloxorz and of games with 2-buttons
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

Cites work

• Computational complexity of two-dimensional platform games
• Gaming is a hard job, but someone has to do it!
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• Lemmings is PSPACE-complete
• Playing games with algorithms: algorithmic combinatorial game theory

Cited in

(8)

• The computational complexity of Angry Birds
• Lemmings is PSPACE-complete
• Classic Nintendo games are (computationally) hard
• The computational complexity of Portal and other 3D video games
• The complexity of speedrunning video games
• Computational complexity of two-dimensional platform games
• Celeste is PSPACE-hard
• All paths lead to Rome

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

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