A recent study from researchers at MIT says that conqueringSuper 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 theWii UgameSuper Mario Makermay 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 inSuper 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 aSuper Mario Bros.level can be classified as “NP-hard.” Although a full explanation as to what constitutes a NP-hard problem can be found onMIT’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 releasedSuper Mario Bros.games are on that level of difficulty, but instead that by using the parts of theSuper Mario Bros.design palette, that NP-hard problems can potentially be created. That’s where the Wii U’sSuper Mario Makercomes into play.Super Mario Makerallows players to create their own levels using the design elements ofSuper 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 completea nearly impossible level created inSuper Mario Maker. So next time you play a fiendishly difficultSuper Mario Makerlevel 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 somemore fun, less torturous, uses for the game.
