Classic Nintendo games are (computationally) hard
| Data(s) |
01/06/2015
|
|---|---|
| Resumo |
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. SCOPUS: ar.j info:eu-repo/semantics/published |
| Formato |
1 full-text file(s): application/pdf |
| Identificador |
uri/info:doi/10.1016/j.tcs.2015.02.037 uri/info:pii/S0304397515001735 https://dipot.ulb.ac.be/dspace/bitstream/2013/230530/1/Elsevier_214157.pdf http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/230530 |
| Idioma(s) |
en |
| Direitos |
1 full-text file(s): info:eu-repo/semantics/restrictedAccess |
| Fonte |
Theoretical computer science, 586 |
| Palavras-Chave | #Informatique générale #Informatique mathématique #Computational complexity #Nintendo games #NP-hardness #PSPACE-hardness #Video games |
| Tipo |
info:eu-repo/semantics/article info:ulb-repo/semantics/articlePeerReview info:ulb-repo/semantics/openurl/article |
