Anybody who has ever smashed a controller has cursed the difficulty of some of Nintendo’s best games. Hey, they don’t call it Nintendo Hard for giggles. But some computer scientists have sat down and proven, once and for all, that Mario is hard.
Believe it or not, this isn’t a bunch of nerds at MIT being cute. That’s the province of the cosplay division of their anime club. It’s like this: there are several different types of problems in computing. Polynomial, function problems, and so on. The toughest nut to crack, though, are NP problems: nondeterministic polynomial.
This isn’t just an academic problem; NP problems are among the most complex in computer complexity theory. And levels in “Super Mario World” and “Zelda”, it turns out, are NP problems.
Why is this more than cutesy puff news? Because it means that these guys have proven that you can potentially solve, or at least do a good job of looking at, NP problems by playing games. This means they can, for example, be turned into games and farmed out to gamers to solve, something gamers have turned out to be pretty good at doing.
OK, so they proved making doing math problems fun means people will do them for free. But, hey, at least we can potentially start cracking some serious NP issues.
image courtesy Nintendo