Classic Nintendo games are (computationally) hard

Classic Nintendo games are (computationally) hard

Show other versions (1)

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 g...

Full description

Bibliographic Details
Main Authors: Aloupis, Greg, Demaine, Erik D, Guo, Alan Xinyu, Viglietta, Giovanni
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Elsevier BV 2019
Online Access:https://hdl.handle.net/1721.1/121347
Description
Summary: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. Keywords: Nintendo games; Video games; Computational complexity; NP-hardness; PSPACE-hardness

Similar Items