Super Mario Bros. is harder/easier than we thought

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

Aaron Williams, G. Viglietta, Erik D. Demaine

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 (7)

• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• The Computational Complexity of Portal and Other 3D Video Games
• The complexity of speedrunning video games
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• Title not available (Why is that?)
• Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets
• The computational complexity of Angry Birds

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)