The hardness of Nintendo, calculated

Computer scientists will, perhaps more deeply than others, appreciate the hardness of several computer games produced by the entity called Nintendo:

"Classic Nintendo Games are (NP-)Hard," Greg Aloupis, Erik D. Demaine [of whose recent work, more here], Alan Guo, arXiv:1203.1895v1, March 9, 2012.

"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., Lost Levels, and Super Mario [pictured here] World; Donkey Kong Country, 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."

(Thanks to investigator Josh Kroll for bringing this to our attention.)