Paper by Erik D. Demaine

Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta, “Classic Nintendo Games are (Computationally) Hard”, Theoretical Computer Science, volume 586, 2015, pages 135–160.

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros. 1–3, The Lost Levels, and Super Mario World; Donkey Kong Country 1–3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

This paper is also available from ScienceDirect and as arXiv:1203.1895.

The paper is available in PDF (3487k).
See information on file formats.
[Google Scholar search]

Related papers:
Nintendo_FUN2014 (Classic Nintendo Games are (Computationally) Hard)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.