MIT Calculates How Hard A Super Mario Brothers Level Can Be

Polynomially hard

If you ever struggled with the legendary Super Mario Bros. games as a kid (or teenager, or adult) you can find a little relief in a new study. Erik Demaine and his team of researchers at MIT came to the decision that Mario’s classic navigating and jumping adventures are hard. Really hard–supercomputer running overtime hard.

The paper, which compared the solutions to Mario games to the kinds of polynomial equations that would make for a less heartwarming Good Will Hunting sequel, found that the building blocks of a Mario level are at that level of difficulty to solve.

In case you don’t remember just how hard it can be at times, take a moment to refresh yourself:

So now that the painful childhood memories have returned, here’s what MIT says to make you feel better. Their analysis, which you can read in more depth, suggests that at its hardest, Mario fits into the “PSPACE” category of equations: requiring exponential time to both solve, and to prove algorithmically.

That doesn’t mean that World 1 Level 1 fits this category–in fact, none of the “commercial” levels in the game necessarily do. But with the building blocks of a Mario level, that difficulty could be achieved fairly easily.

Put simply, according to MIT, “Figuring out how to complete a fiendishly difficult level of “Super Mario Brothers” could take a long time, but so could navigating that level, even with the solution in hand.”

In other words, Mario levels can be really really difficult, whether you know the pathway to the end or not–a fact that Mario Maker level builders have been proving for quite some time already.