Classic Nintendo Games are (NP-)Hard

Details Classic Nintendo Games are (NP-)Hard Classic Nintendo Games are (NP-)Hard

2012-03-08

arxiv.org/abs/1203.1895v1

Computer Science

Computational Complexity

21 pages, 23 figures

Scientific 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.

Affiliated with

Also associated with

No associations

Rating

Classic Nintendo Games are (NP-)Hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classic Nintendo Games are (NP-)Hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classic Nintendo Games are (NP-)Hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-18075