Journal
THEORETICAL COMPUTER SCIENCE
Volume 586, Issue -, Pages 135-160Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2015.02.037
Keywords
Nintendo games; Video games; Computational complexity; NP-hardness; PSPACE-hardness
Categories
Funding
- NSF [CCF-0829672, CCF-1065125, CCF-6922462]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1161626] Funding Source: National Science Foundation
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [1546290] Funding Source: National Science Foundation
Ask authors/readers for more resources
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. (C) 2015 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
