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

I'm canceling my backlog for Apex Legends. Be back never

Live service games like Fortnite and Apex Legends are eating up everyone's time, leaving other games out in the cold. While my backlog continues to grow, it seems the gaming industry is struggling to keep up as well.
Emerging Tech

Ant-inspired walking robot navigates without GPS by using polarized light

What do you get if you cross Boston Dynamics and Ant-Man? You get Antbot, a robot from the French National Center for Scientific Research (CNRS) which uses ant-like navigation to move around without the aid of GPS.
Computing

DLSS is finally arriving in games, but how does Nvidia's super-sampling actually work?

Nvidia's new DLSS technology is exciting, but what is it and how does it work? It's not quite anti-aliasing and it's not quite super sampling. It's a little bit of both and the end results can be impressive.
Home Theater

How to master your equalizer settings for the perfect sound

You may know what an EQ is, but do you know how to adjust equalizer settings for the best possible sound? We go through the basics of the modern EQ and lay out some guidelines for how to achieve tip-top sound from your system.
Movies & TV

'Prime'-time TV: Here are the best shows on Amazon Prime right now

There's more to Amazon Prime than free two-day shipping, including access to a number of phenomenal shows at no extra cost. To make the sifting easier, here are our favorite shows currently streaming on Amazon Prime.
Virtual Reality

Getting into VR is spendy. Which headset is truly worth your hard-earned cash?

Virtual reality has finally gone mainstream, but how do you find the best VR headset for you? Check out a few of our favorites, whether you want the best of the best or a budget alternative for your mobile device.
Gaming

Buy a new Switch console and get a $35 eShop gift card at some retailers

Multiple retailers are currently offering the Neon Blue and Red Nintendo Switch console with a free $35 eShop gift card. The system still costs the standard $300 and includes Joy-Con controllers and the dock.
Gaming

Become a champion with our beginner's guide to Apex Legends

Jumping into Apex Legends for the first time? Need help becoming a champion? Our Apex Legends beginner's guide has 15 tips and tricks that will hopefully help your team make it into the champion's circle.
Gaming

Thrive in the nuclear apocalypse with our Metro Exodus survival guide

Metro Exodus is a difficult shooter, especially if you're new to the series' blend of stealth, action, and scavenging. Here is what you need to know to survive the nuclear apocalypse.
Gaming

Here's where Xur is and what he has for wares this week in Destiny 2: Forsaken

The weekly vendor in Destiny 2: Forsaken always brings Exotic weapons and armor, some of the toughest loot to find in the game. Here's everything you need to know to track down Xur: Where he is, when he shows up, and what he's stocking.
Gaming

How do the revised Xbox One and PlayStation 4 consoles stack up?

Microsoft's new Xbox One S and Sony's PlayStation 4 "Slim" have bucked the generational gaming console trend. But which of these stopgap systems is worth spending your paycheck on?
Gaming

Here's our Champion's guide to picking the best character in Apex Legends

Apex Legends' use of heroes with different abilities helps separate it from other battle royale games. To help you choose your legend, we've put together a legend guide detailing their abilities, strengths, and weaknesses.
Gaming

Transport your Nintendo Switch in style with these nifty cases

The Nintendo Switch, which boasts both wired and handheld modes, needs a good case to ensure it doesn't get beat up while you're on the go. We scoured through dozens of Switch cases to bring you the best ones.
Gaming

These are the best weapons for taking down mutants and bandits in Metro Exodus

Metro Exodus is a very difficult game, and choosing the right weapons is key for surviving the post-apocalyptic Russia that 4A Games has created. These are the best weapons in Metro Exodus.