Classic Nintendo games are (computationally) hard

DOI10.1016/J.TCS.2015.02.037zbMath1327.68113OpenAlexW1749523692MaRDI QIDQ2347007

Erik D. Demaine, Giovanni Viglietta, Alan Guo, Greg Aloupis

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.02.037

zbMATH Keywords

computational complexityNP-hardnessPSPACE-hardnessvideo gamesNintendo games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

Push-Pull Block Puzzles are Hard ⋮ Trainyard is NP-hard ⋮ Games, Puzzles and Treewidth ⋮ Unnamed Item ⋮ Optimizing the Video Game Multi-Jump: Player Strategy, AI, and Level Design ⋮ The complexity of speedrunning video games ⋮ Restricted Power - Computational Complexity Results for Strategic Defense Games ⋮ Mario Kart Is Hard ⋮ Cooperating in video games? Impossible! Undecidability of team multiplayer games ⋮ Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible ⋮ On a generalization of ``eight blocks to madness puzzle ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Inventory control under speculation: Myopic heuristics and exact procedures

Cites Work

• Gaming is a hard job, but someone has to do it!
• Lemmings is PSPACE-complete
• Computational Complexity of Two-Dimensional Platform Games

This page was built for publication: Classic Nintendo games are (computationally) hard