Paper by Erik D. Demaine
- Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta, “Classic Nintendo Games are (Computationally) Hard”, in Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 1–3, 2014, pages 40–51.
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, 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.
- The full paper is available as arXiv:1203.1895.
- The paper is available in PDF (909k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 3, 2017 by