# Scientists prove playing ‘Super Mario Bros.’ can be as hard as complex math

If you’ve found that solving the most challenging levels of Super Mario Maker can be as taxing as your toughest college mathematics problem sets, you’re not alone, and now there’s scientific research to back you up. According to MissOpen, a team of artificial intelligence and computer science researchers from the Massachusetts Institute of Technology (MIT) recently published a study showing that beating a level in Nintendo’s seminal platformer is “as hard as the hardest problem in the ‘complexity class’ PSPACE.”

To explain what that means, first we have to address what “complexity class” means. Computer scientists are not just concerned with solving complicated problems, but also with how quickly and efficiently those problems can be solved, given the real-world constraints of working with finite time and computing power. For the sake of easy comparison, all of these considerations are made assuming that you are doing the calculations with a Turing Machine, the rudimentary computer featuring a single, infinite tape that was conceived of by computing, cryptography, and AI pioneer Alan Turing and proven to be functionally equivalent to all digital computers as we currently understand them.

Related Videos

“P”-class problems are those where the relationship between the number of elements involved in the problem (N) has a polynomial (hence the “P”) relationship to the amount of time it takes. That means that the time to solve can be expressed in an equation that involves performing basic operations on N or N raised to various powers (N-squared, N-cubed, etc).

An example of a P problem would be determining which number from a set is the highest. Because you would only need to check each number once and record the highest encountered, the time to solve scales directly to how large the set is. The alternative is an exponential relationship between N and the time to solve, involving numbers raised to the Nth power, which can take orders of magnitude longer.

Encompassing the set of all P problems is “NP” (non-deterministic polynomial), where a solution can be quickly verified by an algorithm in polynomial time, but it can’t necessarily be solved in the first place as efficiently. A classic example is determining the prime number factors of an arbitrarily large number.

Determining whether or not P = NP (i.e., whether any problem that can be easily checked can also be easily solved) is one of the biggest questions looming over mathematics and computer science, so much so that the Clay Mathematics Institute listed it as one of its seven Millennium Problems, the solutions to which have a \$1 million bounty each. While mathematicians generally agree that P is likely not equivalent to NP, no one has definitively proven the case either way. The problem has garnered enough attention to have several pop culture references, such as in the above episode of The Simpsons, or multiple allusions on Futurama.

An even larger set of problems, however, is called PSPACE, encompassing the sets of both P and NP problems. PSPACE refers to problems where there is a polynomial relationship between the number of elements involved in the problem and the amount of space required to compute a solution (i.e., how much memory the computer needs). Looping back to where we started, the researchers showed that Super Mario Bros. levels can be among the most difficult to solve of the PSPACE problems.

“The paper doesn’t attempt to establish that any of the levels in commercial versions of Super Mario Brothers are that hard,” the team pointed out, “only that it’s possible to construct PSPACE-hard levels from the raw materials of the Super Mario world.” Anyone familiar with the fan-made levels from Super Mario Maker can attest to the fact that the upper limit for complexity in levels made from the elemental Mario components is extremely high.

The discrete rules and emergent complexity of video games have made them an excellent test bed for all sorts of AI and computer science experiments that could find applications in the real world. “Mathematically, video games are not very different from computational models of real-world physical systems, and the tools used to prove complexity results in one could be adapted to the other,” the team added.

“I’m really excited about these kinds of hardness proofs, and I’ve been pushing them a lot in the last couple years,” explained lead author Erik Demaine. “My hope is to encourage more people to do this, because it really does build up a lot of expertise that makes it easier to conquer problems. 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 limitations of algorithms.”

#### Editors' Recommendations

Topics
That \$2 million Super Mario Bros. auction may have been rigged

Complete-in-box retro games have been in the news a lot lately due to their sale prices rising. The most famous recent example of this phenomenon is a copy of Super Mario Bros. for the Nintendo Entertainment System selling for \$2 million. In a video investigation, journalist Karl Jobst claims that the grading company, Wata Games, and the auction company, Heritage Auctions, behind these sales are artificially raising the value.

Exposing FRAUD And DECEPTION In The Retro Video Game Market

You can now replay PS3 classics with AMD Super Resolution

AMD's FidelityFX Super Resolution (FSR) isn't exclusive to individual games, it seems. RPCS3 -- the go-to emulator for PlayStation 3 on PC -- added support for the feature over the weekend, and it's the first emulator to do so. Hopefully, it'll kick off a stream of support from other emulators, too.

The latest RPCS3 build supports FSR, so all you need to do is install the latest version or update the version you have, and you'll be able to use FSR with your favorite PS3 games. To enable the feature, follow Configuration > GPU in the app, tick the Enable FSR Upscaling box, and set the strength of the sharpening filter.

Mario Golf: Super Rush has boss fights and a thunder-summoning sword

It’s been a long, long time since Mario Golf has appeared on a Nintendo home console. Fans got a portable Nintendo 3DS installment in 2014, but the last proper console version was 2003’s Mario Golf: Toadstool Tour on the Nintendo GameCube. To put that into perspective, that means the franchise has missed the Nintendo motion control era entirely in its nearly 20-year absence.

Considering the gap, Mario Golf: Super Rush has a lot of lost time to make up for. The developers at Camelot appear to be up to that challenge with what’s looking like a fairly robust Nintendo Switch game that balances traditional golf, RPG gameplay, and some creative new topspin on the established format.