Classic Nintendo Games are (NP-)Hard
March 13, 2012 11:01 AM Subscribe
Some (slightly generalized) classic Nintendo games are NP-Hard. [pdf]
From the paper:
From the paper:
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 Super Mario Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing games. For Mario and Donkey Kong, we show NP-completeness. In addition, we observe that several games in the Zelda series are PSPACE-complete...
For these games, we consider the decision problem of reachability: given a stage or dungeon, is it possible to reach the goal point t from the start point s? If it is hard to decide even this question, then it is certainly hard to find an optimal path. Our results apply to generalizations of the games where we only generalize the map size and leave all other mechanics of the games as they are in their original settings. All of our NP-hardness proofs are by reduction from 3-SAT, and the proofs for Mario, Donkey Kong, Legend of Zelda, and Metroid rely on a common construction, while the proof for Pokemon is based on a reduction to Push-1. We show that certain Zelda games are in fact PSPACE-complete, by reducing from PushPush-1.Wikipedia on NP-Hard problems and the 3-SAT problem.
This thread has been archived and is closed to new comments