  We prove NP-hardness results for five of Nintendo's largest video game
franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. 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 Pokemon role-playing games. In addition, we
prove PSPACE-completeness of the Donkey Kong Country games and several Legend
of Zelda games.
