Classic Nintendo Games Are NP-Hard

mikejuk writes "You may have have thought games like Super Mario Bros., Donkey Kong, and so on were hard at the time you were playing them, but you probably didn't guess they were NP-hard. Now we have some results from computer scientists at Universite Libre de Bruxelles and MIT Computer Science and Artificial Intelligence Laboratory that many classic games contain within them an NP-hard problem. It has been proven that the following game franchises are NP-hard (PDF): Mario, Donkey Kong, Legend of Zelda, Metroid and Pokemon. At least you now have an excuse for your low scores."

Comments

I'm sure ...

[gstoddart]

I'm sure I've seen this before. Ahh, yes here it is, almost two years ago.

I guess not the exact same thing, since the last story didn't explicitly mention Donkey Kong ... but certainly the NP-hard part has been discussed for a while.

Re:What?

[Anubis IV]

For an intro to NP and NP-hard, might I suggest Wikipedia's entry on NP-hard? You get to stuff like this in any classes that cover computational complexity, such as coursework covering algorithms. NP comes up every few weeks on Slashdot since it's an interesting-ish topic for most of us.

For a gentler introduction

[tepples]

There are three classes of problems at issue here:

• NP, problems for which you can verify a solution in polynomial time (e.g. O(x^2) or O(x^3) operations);
• NP-hard, problems that are at least as hard as the hardest problems in NP; and
• NP-complete, problems that are both NP and NP-hard.

For a gentler introduction, see P vs. NP.

Re:What?

[Oxford_Comma_Lover]

"Not polynomial."

It refers to the complexity of a computing problem being significant enough that it cannot be guaranteed to be solved in polynomial time.

So doing an operation on a two digit number is easy, but as the number of digits goes up, and you try to do the same operation on the bigger numbers, it gets harder at a rate which is greater than polynomial with the size of the input.

It's a little more complex than that, but that's basically it.

Super Mario Forever IPS

[tepples]

The IPS file for Super Mario Forever, the map pack featured in the Super Mario Frustration video, is still available.

Re:Kid Icarus

[gauauu]

I never could get past that lava jet ski level!

I could whoop up all the way there and I kept getting just a little bit further, but then, nothin.
I'll bet the final baoss wasn't that hard!

No, the final boss level (and final boss) were as tough as the rest of the game. I spent a couple months in college where I dug out my old nes and vowed to beat Battletoads (on the real thing, with no save state cheating). It was incredibly painful. It was hard all the way through. The only real hope you have is juggling the vultures on the 2nd level to gets tons of 1-ups.

Re:What?

[SorcererX]

NP is "Nondeterministic polynomial", not "Not polynomial."