Super Mario Bros. is harder/easier than we thought

DOI10.4230/LIPICS.FUN.2016.13MaRDI QIDQ5282811zbMATHOpenAlexFDO

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

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)

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

Cited in

(12)

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

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)