It Is On, Like Donkey Kong

Many of the games in the Mario, Donkey Kong, Legend of Zelda, Metroid and Pokémon series prove to be NP-hard. That means deciding whether a player can complete them is at least as hard as the hardest problems in NP, a complexity class involved in the tantalising problem of P versus NP

via Mario is hard, and thats mathematically official – 14 March 2012 – New Scientist.