Classic Nintendo games are (computationally) hard
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121347 |
| _version_ | 1826209911865868288 |
|---|---|
| author | Aloupis, Greg Demaine, Erik D Guo, Alan Xinyu Viglietta, Giovanni |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Aloupis, Greg Demaine, Erik D Guo, Alan Xinyu Viglietta, Giovanni |
| author_sort | Aloupis, Greg |
| collection | MIT |
| description | 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 |
| first_indexed | 2024-09-23T14:35:04Z |
| format | Article |
| id | mit-1721.1/121347 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:35:04Z |
| publishDate | 2019 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1213472022-10-01T21:46:57Z Classic Nintendo games are (computationally) hard Aloupis, Greg Demaine, Erik D Guo, Alan Xinyu Viglietta, Giovanni Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 2019-06-18T19:04:13Z 2019-06-18T19:04:13Z 2015-06 2019-06-18T12:28:41Z Article http://purl.org/eprint/type/JournalArticle 0304-3975 https://hdl.handle.net/1721.1/121347 Aloupis, Greg et al. "Classic Nintendo games are (computationally) hard." Theoretical Computer Science 586 (June 2015): 135-160 © 2015 Elsevier B.V. en http://dx.doi.org/10.1016/j.tcs.2015.02.037 Theoretical Computer Science Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Aloupis, Greg Demaine, Erik D Guo, Alan Xinyu Viglietta, Giovanni Classic Nintendo games are (computationally) hard |
| title | Classic Nintendo games are (computationally) hard |
| title_full | Classic Nintendo games are (computationally) hard |
| title_fullStr | Classic Nintendo games are (computationally) hard |
| title_full_unstemmed | Classic Nintendo games are (computationally) hard |
| title_short | Classic Nintendo games are (computationally) hard |
| title_sort | classic nintendo games are computationally hard |
| url | https://hdl.handle.net/1721.1/121347 |
| work_keys_str_mv | AT aloupisgreg classicnintendogamesarecomputationallyhard AT demaineerikd classicnintendogamesarecomputationallyhard AT guoalanxinyu classicnintendogamesarecomputationallyhard AT vigliettagiovanni classicnintendogamesarecomputationallyhard |