Playing Nintendo Games is Hard

Yup, one of the world's most important mathematical problems has finally been solved: some of the classical Nintendo games are NP-hard. In fact, several games in the Legend of Zelda series are also PSPACE-complete.

One of the authors of this paper is Erik Demaine, a brilliant young mathematics professor at MIT who also has a history of doing research on quirky problems. (I strongly suspect that an Ig Nobel Prize is in his future---perhaps even for this bit of research.)

One thing that would interest me about the puzzles in these various games is if such a result still holds when only considering the subset of "reasonable" (or perhaps even "good") moves. Essentially, I want to see a result of the computational complexity in more "practical" circumstances. On at least a philosophical level, this is similar to the idea of the worst-case scenario being hard but getting a good or good enough solution (say, a "good" local optimum, which could perhaps take more than the theoretically minimal number of steps) is easy in practice.

I'd be very interested in what some of you CS folks think about this stuff.

(Tip of the cap to Louis Wang, who posted a link to the Kotaku article on Facebook. I have chosen to link directly to the scientific article on the arXiv.)