Skip to main content

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

Super Mario Maker
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.

Recommended 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.

P = NP
The Simpsons via frinkiac.com

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.

By Hand drawn in Inkscape Qef - Own work by uploader, intended to replace bitmap image illustrating same thing, Public Domain, https://commons.wikimedia.org/w/index.php?curid=4353102
Wikimedia Commons

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.”

Will Fulton
Former Digital Trends Contributor
Will Fulton is a New York-based writer and theater-maker. In 2011 he co-founded mythic theater company AntiMatter Collective…
The Super Mario Bros. movie is delayed to April 2023
Mario with a shocked expression.

Mario fans are going to have to wait a little bit longer for their cinematic Christmas present. Nintendo and Illumination have announced that the release of the CGI-animated Super Mario Bros. movie has been delayed to April 2023.

The film, which has been in production since 2018, was originally slated to come out in theaters on December 21, 2022. But on Monday night, Nintendo director and Super Mario creator Shigeru Miyamoto and Illumination founder and CEO Chris Meledandri, who helmed the iconic Despicable Me film series, announced on Twitter that the release date for the movie was pushed back to April 7, 2023, for North America and April 28, 2023, for Japan after consulting with each other.

Read more
That $2 million Super Mario Bros. auction may have been rigged
2 million super mario auction bros

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

Read more
Sealed Super Mario Bros. game auctioned for a whopping $660,000
Mario twirls his cap in front of New Donk City in Super Mario Odyssey.

A factory-sealed copy of Nintendo’s Super Mario Bros. game bought 35 years ago has fetched an incredible $660,000 at auction.

The sale was handled by Dallas-based Heritage Auctions and took place on Friday, April 3. The identities of the seller and buyer have not been revealed.

Read more