Classic Nintendo games are (computationally) hard

DOI10.1016/J.TCS.2015.02.037MaRDI QIDQ2347007zbMATH OpenOpenAlexFDO

Authors Greg Aloupis, Erik D. Demaine, Alan Guo, 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.02.037

zbMATH Keywords

computational complexityNintendo gamesNP-hardnessPSPACE-hardnessvideo games

Mathematics Subject Classification ID

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

Recommendations

• Super Mario Bros. is harder/easier than we thought
• Gaming is a hard job, but someone has to do it!
• Computational complexity of two-dimensional platform games
• The computational complexity of Portal and other 3D video games
• Mario Kart is hard

Cites work

• Computational complexity of two-dimensional platform games
• Gaming is a hard job, but someone has to do it!
• Lemmings is PSPACE-complete

Cited in

(23)

• Trainyard is NP-hard
• Inventory control under speculation: Myopic heuristics and exact procedures
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• Mario Kart is hard
• Bust-a-Move/Puzzle Bobble is NP-complete
• The computational complexity of Portal and other 3D video games
• The complexity of speedrunning video games
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• Restricted Power - Computational Complexity Results for Strategic Defense Games
• Computational complexity of motion planning of a robot through simple gadgets
• Computational complexity of two-dimensional platform games
• Optimizing the video game multi-jump: player strategy, AI, and level design
• Gaming is a hard job, but someone has to do it!
• Games, Puzzles and Treewidth
• Planar 3-SAT with a clause/variable cycle
• Super Mario Bros. is harder/easier than we thought
• Push-pull block puzzles are hard
• Celeste is PSPACE-hard
• The Legend of Zelda: the complexity of mechanics
• Puzzle and dragons is hard
• All paths lead to Rome
• On a generalization of ``eight blocks to madness puzzle

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

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