In computer science, there’s no problem scarier than an NP-hard problem. These are the tough-as-hell issues computers struggle with, like the traveling salesman problem. It is the cutting edge of computer science, and it sounds intimidating. But it turns out, you might have already built one, if you happen to have a Wii U.
MIT, America’s elite nerd squad, took a look at the elements of the game and determined it was possible to build an NP-hard level in the game. They didn’t test all the levels to determine exactly where they fit in the continuity of computer science problems, called PSPACE, but examining the elements of the game, they’ve found it can be engineered to deliver NP problems.
The example they use is a pretty common Mario problem: A spiny trapped between two pipes that you need to get around. The spiny’s dilemma is, believe it or not, a demonstration of an NP problem, the halting problem. If left alone, will that spiny just walk back and forth forever? Now what if Mario bumps that spiny over one of the pipes? What happens to it then? And that’s not even getting into what people have engineered with the tools Nintendo has given them.
This is useful for more than just sticking it to that ten-year-old who keeps beating your Mario Maker levels. Video games are, among other things, simulations of physical systems, and that means we could design NP problems and unleash them on the internet for people to beat, or pull ideas and tools from video games to use for industrial modeling of physical systems. So, look at it this way: All that controller-chucking you did as a kid was ultimately for the common good of humanity.
(Via MIT)