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.

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

Gaming

‘Kingdom Hearts III’ out in the wild, director asks for support to stop spoilers

Kingdom Hearts III has been leaked, with several copies of the game out in the wild. The game's director, Tetsuya Nomura, responded to the situation, calling for help from gamers to stop spoilers from spreading online.
Movies & TV

The best shows on Netflix, from 'Haunting of Hill House’ to ‘Twilight Zone’

Looking for a new show to binge? Lucky for you, we've curated a list of the best shows on Netflix, whether you're a fan of outlandish anime, dramatic period pieces, or shows that leave you questioning what lies beyond.
Home Theater

The best movies on Netflix in December, from 'Buster Scruggs’ to endangered cats

Save yourself from hours wasted scrolling through Netflix's massive library by checking out our picks for the streamer's best movies available right now, whether you're into explosive action, witty humor, or anything else.
Gaming

The 25 best SNES games

The Super Nintendo Entertainment System might be the greatest game console ever made, but what are the best titles for the system? Here are our picks for the best SNES games, including A Link to the Past and Chrono Trigger.
Gaming

How do Nintendo Switch, Xbox One X compare to each other? We find out

The Nintendo Switch is innovative enough to stand apart from traditional consoles, but could it become your primary gaming system? How does the Switch stack up against the Xbox One?
Gaming

Sharing your best gameplay moments is quick and easy on the Xbox One

The current generation of consoles make it easier than ever to share your gaming highlights with the world. Here's a quick guide on how you can record a gameplay video on Xbox One.
Gaming

The history of Battle Royale: From mod to worldwide phenomenon

Battle royale games like PlayerUnknown's Battlegrounds’ and Fortnite have become the biggest trend in video games. The genre is also pushing the envelope in streaming and eSports in a way that might hint at the future of the industry.
Gaming

The DualShock 4 is one of the best controllers ever, and you can use it with a PC

Sony's new DualShock 4 controller has become a fan favorite, and some people want to use it with a PC. Here's how to connect your DualShock 4 and start using it, either with an official adapter, or unofficial software.
Gaming

Project Stream testers get to keep a free copy of ‘Assassin’s Creed Odyssey’

Those who participated in Google's technical test of Project Stream won't be able to access the service to play Assassin's Creed Odyssey after January 15, but they'll get to keep the game on PC anyway.
Gaming

Newest ‘Destiny 2’ raid already completed by two-person team

The latest raid in Destiny 2: Forsaken is Scourge of the Past, and a two-person team has already managed to complete it. The task took 15 hours of trial-and-error effort before the duo managed to take down the final boss.
Deals

Need a discounted Xbox bundle by Christmas? Walmart has you covered

Black Friday and Cyber Monday have both come and gone, but you can still save some cash on a new Xbox One bundle at Walmart. Both the Xbox One S and the Xbox One X are on sale now.
Gaming

With our Steam guide, you can give the gift of gaming this holiday season

The holidays may have passed, but it's always a good time to give the gift of gaming (especially when there's a Steam sale)! Here's our quick guide on how to give a Steam game as a gift.
Gaming

‘Fortnite’ update 7.10 brings a rotating selection of modes big and small

The latest update for Fortnite introduces 14 Days of Fortnite, an event that brings back large and small battle royale modes as well as brand new ones to enjoy during the holiday season.
Gaming

New Xbox consoles are reportedly code-named ‘Anaconda’ and ‘Lockhart’

Microsoft's next-generation Xbox plans reportedly consist of two separate consoles. One, called "Lockhart," is a more affordable machine, while "Anaconda" is designed with more horsepower.