A recent study from researchers at MIT says that conquering Super Mario Bros. levels can be just as tough as solving high-level mathematical problems.
Those who have been stumped by some of the hardest fan-made levels in the Wii U game Super Mario Maker may not have to feel so bad about their failure to clear them. A recent study conducted by MIT’s Computer Science and Artificial Intelligence Laboratory says that completing a level in Super Mario Bros. can be “very, very hard,” on the same level as some of the hardest and time-consuming mathematical problems.
The study defined the toughest challenges possible in a Super Mario Bros. level can be classified as “NP-hard.” Although a full explanation as to what constitutes a NP-hard problem can be found on MIT’s official website, here’s an attempt to explain NP in its most uncomplicated form. In the world of theoretical computer science, there exists a number of still-unsolved problems and theories, called PSPACE problems. NP means nondeterministic polynomial time and is a way to describe how long it takes to solve a complex mathematical problem. An NP problem is one that exists on the upper scale of that spectrum, requiring a long time and lots of systematic computation to solve.
The study doesn’t claim that levels in commercially released Super Mario Bros. games are on that level of difficulty, but instead that by using the parts of the Super Mario Bros. design palette, that NP-hard problems can potentially be created. That’s where the Wii U’s Super Mario Maker comes into play. Super Mario Maker allows players to create their own levels using the design elements of Super Mario Bros., which means that PSPACE problems of NP-hard difficulty can be created using the game.
According to the study, the difficulty goes further than just knowing the solution of such a complex problem:
Like NP, PSPACE contains problems that appear to require exponential time to solve. But the hardest problems in PSPACE — the PSPACE-hard problems — also take exponential time to verify. In some sense, that makes PSPACE a natural place for a video game to reside. 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.
That could explain why it took so long (nearly 46 hours) to complete a nearly impossible level created in Super Mario Maker. So next time you play a fiendishly difficult Super Mario Maker level and manage to finish it after hours of struggling, you can take pride in knowing you beat something that mathematicians consider to be extraordinarily difficult. Or alternatively, you could just enjoy some more fun, less torturous, uses for the game.
Super Mario Maker is available now, exclusively on Wii U.
Source: MIT CSAIL