Apparently, Super Mario is NP-complete. Zelda is PSPACE-complete.
Conclusion: Games are hard. Alternatively, we can all play games to solve hard problems in a fun way…
Russel Impagliazzo‘s great article on possible outcomes of P-NP
The Status of P versus NP Problem (as of September 2009), by Lance Fortnow