A new MIT study has shown that the old concept of Nintendo Hard might be a bit more scientific than you'd think.
A group of researchers have analyzed the computational complexity of a number of classic Nintendo franchises, including Mario, The Legend of Zelda, and Pokemon, and discovered that they fall into a class of problems called NP-hard.
To understand exactly what that means, we'll need to get a bit of background in math. I know, I know, no one goes to a gaming site to learn, but trust me, this stuff is actually pretty fascinating.
In mathematical theory, many problems fall into one of two categories, P and NP. P problems are those that can be solved with an algorithm relatively efficiently — they'll still take longer to solve as the problem gets more complex, but the time required won't increase exponentially. NP problems, on the other hand, are those where a given solution can be checked efficiently by an algorithm. All P problems are NP (since anything that can be solved can be checked just as efficiently), but there are plenty of NP problems that don't have efficient solutions.
One famous example of this is the travelling salesman problem: If a salesman needs to visit 100 different cities, what's the shortest route he can take between all the locations? There are plenty quick and easy ways to check a given solution, but coming up with one from scratch will take a long time, and it'll only get exponentially longer as you add more cities.
This new MIT study proved that determining whether it's possible to complete a given level in Mario, Metroid, Donkey Kong and other classic Nintendo games is at least as hard as the hardest problems in this NP group, meaning the games can be categorized as NP-hard.
To accomplish this, they constructed custom levels for each game that took advantage of their unique gameplay properties. Not every level was solvable, and they analyzed exactly what it would take to determine whether or not a given configuration of enemies, items, or geometry would actually allow the player to make it to the end of the level. Turns out, it's a pretty tricky problem for a computer to solve, and that's why both designing and playing through a level in an old school platform requires quite a bit of creative thinking.
But the results didn't stop there. The team also found that some of the games they studied, including Super Mario Bros., Donkey Kong Country, and Metroid, fall into a class of problems that's more important than NP-hard, something called NP-complete.
So what makes NP-complete problems so special? Well, it turns out that there's a fairly important debate going on in the mathematics world about whether or not all NP problems are, in fact, P problems. It might be that all NP problems are just P problems we haven't discovered efficient solutions for yet, but it could just as easily be true that some NP problems are impossible to solve efficiently. This question, whether P=NP, is so important that one group is offering a million dollar prize to anyone who can conclusively answer it one way or the other.
NP-complete problems are unique in that an efficient solution to any one of them could be adapted to all NP problems efficiently, thus proving that P=NP and ending the debate once and for all.
Thanks to this study, we now know that if you could develop an efficient algorithm that could determine whether it was possible to get from point A to point B in Super Mario Bros., you'd have solved one of the most important problems in computer science and win a million dollars in the process.
I wouldn't hold your breath, though. One recent poll found that 81% of researchers in the field believe P does not, in fact, equal NP. If they're right, that means it'd impossible to ever come up with an efficient solution to Mario, Zelda, or any other NP-complete problem.
If you're interested in reading the complete study, you can find it here in all of its jargon-filled glory.
