Paper by Erik D. Demaine

Reference:

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.

Abstract:

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.

Comments:

The full paper is available as arXiv:1203.1895.

Availability:

The paper is available in PDF (909k).

See information on file formats.

[Google Scholar search]

Related papers:

Nintendo_TCS (Classic Nintendo Games are (Computationally) Hard)