If youâ€™ve ever been frustrated at your inability to complete a level of Super Mario Brothers, hereâ€™s a little something to cheer you up. Computer scientists have demonstrated that solving a level in the popular video game is tantamount to solving some of the hardest problems in computational science.

Theyâ€™re known as â€śNP hardâ€ť problems, as opposed to the class known as â€śPâ€ť problems, which are relatively easy to solve. A classic example of an NP hard problem is the Traveling Salesman problem: the salesman must find the shortest route to visit 100 cities.

It turns out that navigating the levels of *Super Mario Brothers* can be equivalent to solving these very difficult mathematical equations, according to MIT computer scientist and engineer Erik Demaine. One caveat: Demaine and his colleagues havenâ€™t shown that the actual levels in commercial versions of *Super Mario Brothers* meet this standardâ€”only that it is possible to construct levels that are NP hard using the raw materials of the game world, a task thatâ€™s actually possible with *Super Mario Maker*. More on this in a second.

Computer scientists are particularly interested in NP problems, because theyâ€™re the cornerstone of cryptography. As MITâ€™s Larry Hardesty explained in 2009:

Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists donâ€™t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.

Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: thereâ€™s no way around that. But if it simply keeps a record of the largest number itâ€™s seen so far, it has to look at each entry only once. The algorithmâ€™s execution time is thus directly proportional to the number of elements itâ€™s handling â€” which computer scientists designate N.

Advertisement

So if youâ€™ve got an algorithm to find the largest number in a list of 100 numbers (N=100), the time it takes to complete the task is proportional to Nâ€”letâ€™s say one second per operation. Things get more complicated if your algorithm is tasked with, say, figuring out the distances between a given number of airports on a map (where N is the number of airports). It takes longerâ€”three hours rather than one secondâ€”because for every airport on the map, the algorithm must calculate the distance to all the others. The real trouble comes with exponential algorithmsâ€”say, to factor a 1000-digit number. Then it would take a whopping* 300 quintillion years* to complete the task.

Thatâ€™s how long it takes to solve such a problem on its own, but if a computer is given the answer, it can quickly verify that the answer is correct. Think of it as being like a riddle: itâ€™s hard to guess the answer, but once weâ€™re told, the answer seems obvious.

Advertisement

So what does all of this possibly have to do with *Super Mario Brothers*? A couple of years ago, Demaine and his colleagues examined a generic version of a video game structure they dubbed a â€ślocked door.â€ť This version had two possible states for a path through the game: itâ€™s either safe to use that path, or it is not. Those two states, open or closed, can correspond to the 0s and 1s of computer memory bits.

Advertisement

Demaine *et al*. demonstrated that any computational problem could be represented by locked doors organized in just the right configuration. If a given problem is exponentially hard, so, too, will be figuring out how to complete that game level. In other words, that problem is NP hard.

Using the raw materials of the game world, they figured out how to construct these kinds of locked doors in *Donkey Kong Country*. They failed to do the same for *Super Mario Brothers*. They thought building a locked door in *Super Mario* was impossible and concluded that the game was at least as hard as the most difficult NP problems. But they couldnâ€™t definitively *prove* that it was harder. For mathematicians, thatâ€™s a key distinction.

Advertisement

At the International Conference on Fun with Algorithms taking place this week in La Maddalena, Italy, Demaine will describe how the key to building a locked door in *Super Mario Brothers* is to exploit a monster called a â€śspiny.â€ť A spiny can move between two barriers in the game but canâ€™t leap over themâ€”not without Marioâ€™s help, anyway. If Mario bumps the floor just as the spiny approaches the barrier, it pops right over. The locked door Demaine *et al*. eventually constructed is based on which side of a barrier the spiny is on. If itâ€™s on one side, the path is open; if itâ€™s on the other side, the path is closed. And there are separate paths that allow Mario to bump the spiny from one side to the other.

Advertisement

And hereâ€™s why itâ€™s not just about video games. Mathematicians and computer scientists often talk about proving the general statement that P does not equal NP. If P does not equal NP, then there is no fast, general way to solve NP hard problems. Conversely, if P does equal NP, that would mean that even seemingly difficult problems could have fast, easy solutions. We just havenâ€™t found them yet. And that has enormous implications for cryptography. All our protected data would become vulnerable. (For what itâ€™s worth, most mathematicians believe itâ€™s far more likely that P does not equal NP.)

Confused? Hereâ€™s Simon Singh, author of *The Simpsons and Their Mathematical Secrets*, giving his own take on P vs NP, illustrated with short clips from *The Simpsons* and *Futurama*:

For such an arcane mathematical concept, P vs NP gets cited a lot in popular culture. Itâ€™s served as a plot point in *Elementary.* And Charlie Epps, the brilliant mathematician played by David Krumholtz in *Numb3rs*, used the game Minesweeper to explain the concept to a group of FBI agents in an early episode.

Advertisement

Demaine has taught a class on such hardness proofs using video games, and thinks this can be an effective educational approach. â€śMy hope is through this class and these kinds of papers to encourage more people to do this, because it really does build up a lot of expertise that makes it easier to conquer problems,â€ť he said in a statement. â€śThe more practice we get as a collective, the better we are at solving these types of problems. And itâ€™s important to know the limits of algorithms.â€ť

[MIT]

Advertisement