| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435868 | Theoretical Computer Science | 2015 | 26 Pages |
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, 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Greg Aloupis, Erik D. Demaine, Alan Guo, Giovanni Viglietta,