Computer Scientists Built an Uber Hard Theoretical 'Super Mario' Level

Theoretical computer science is among the most esoteric, brain-numbing fields a person could attempt to wrap her head around. Perhaps that’s why some academics are putting up such an effort to inject some fun and humanity into it. And by humanity, we mean pixelated Italian plumber brothers in overalls.

A level of the video game Super Mario Bros. could theoretically be really, really hard — so hard that all the computational power in the world working on the problem for the lifetime of the universe would never pass the level, even though it is technically passable.

This bit of insight comes from a group of computer scientists from MIT, the University of Ottawa, and Bard College at Simon’s Rock, who have written a proof that the Super Mario world could theoretically host an algorithm in the complexity class known as PSPACE.

Their article will be presented next week in Italy at the International Conference on Fun with Algorithms. (Yes, really.)

To explain what this means, we’re going to have to back up a bit. Theoretical computer scientists spend a great deal of time thinking about the complexity of algorithms. It’s an important question, because the difficulty of a problem determines whether it could be solved by a computer in a meaningful amount of time. If a problem is highly complex, and can’t be made simpler, there’s no point wasting brain power and computational energy trying to solve it.

A famous example of this theoretically hard problem is factoring a 1,000-digit number. The computation required to test all of the possibilities is enormously vast — there are just too many possible combinations. But verifying if a given number is a factor of that 1,000-digit number isn’t hard — your smartphone could do it. For this reason, this problem is in the complexity class called NP, which comprises algorithms that are very difficult to solve, but possible to verify.

The PSPACE class is a significant level up in difficulty from NP. In PSPACE, both solving and verification are nearly impossible. The authors of this article had previously proved that Super Mario Bros. could be in the NP class of difficulty — this new work takes the game to the next level.

Here’s how they did it: The researchers have previously described a video game feature called a locked door — it involves a passageway that has two states, passable or impassable, and a way for the player to cause a switch between the two. In this way, a locked door serves as a piece of computational circuitry. The right configuration of locked doors could produce a theoretical level that is both exponentially hard to solve and exponentially hard to verify — and therefore in the PSPACE complexity class.

Before now, the researchers didn’t think there were any locked doors in Super Mario land — and didn’t think they could be built with the materials available. “We thought it was impossible,” co-author and MIT professor Erik Demaine says.

But on a closer inspection, they found one: If you put an enemy so that it blocks a passageway and can only be removed by bumping him over a barrier and out of the way from below, then this configuration functions as a locked door. Enough of these, and you can build a level in PSPACE.

Of course, this level will never exist, and wouldn’t be fun to play if it did. So why all the trouble? Its all about having Fun With Algorithms. And what computer science kid doesn’t also love retro video games?

“It’s a simple, natural way to attract students to study this specific topic,” says Fabrizio Grandoni, a research professor at the University of Applied Sciences and Arts of Southern Switzerland.

Demaine teaches a whole MIT class on how working on algorithm hardness proofs is secretly a really good time. You can watch the lectures online and even complete the class assignments and projects, if you’re feeling left out of the fun.