期刊
THEORETICAL COMPUTER SCIENCE
卷 586, 期 -, 页码 135-160出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2015.02.037
关键词
Nintendo games; Video games; Computational complexity; NP-hardness; PSPACE-hardness
资金
- 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
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据
分享论文
