Super Mario Bros. is harder/easier than we thought

DOI10.4230/LIPICS.FUN.2016.13zbMATH Open1369.68237OpenAlexW2412311009MaRDI QIDQ5282811FDOQ5282811

Authors: Erik D. Demaine, Aaron Williams, G. Viglietta 

Publication date: 17 July 2017

Full work available at URL: https://doi.org/10.4230/LIPIcs.FUN.2016.13

Recommendations

• Classic Nintendo games are (computationally) hard
• Computational complexity of two-dimensional platform games
• Gaming is a hard job, but someone has to do it!
• Mario Kart is hard
• The computational complexity of Portal and other 3D video games

zbMATH Keywords

computational complexityPSPACEvideo gamesSuper Mario Bros.

Mathematics Subject Classification ID

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

Cited In (12)

• Computational complexity of motion planning of a robot through simple gadgets
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• Celeste is PSPACE-hard
• The complexity of speedrunning video games
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• Mario Kart is hard
• Gaming is a hard job, but someone has to do it!
• Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets
• The computational complexity of Portal and other 3D video games
• The computational complexity of Angry Birds
• Classic Nintendo games are (computationally) hard
• Computational complexity of two-dimensional platform games

This page was built for publication: Super Mario Bros. is harder/easier than we thought

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