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

Computing

The Keystone keyboard powers your typing or gaming with built-in A.I.

A new keyboard from Input Club, called Keystone, aims to improve consumer's typing response and accuracy by including an adaptive A.I. process in the hardware. By finding patterns in typists' behavior, it adapts for greater efficiency.
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.
Gaming

Did your PS1 favorite make our list of the best PlayStation games?

Take a stroll down memory lane with the 50 best games ever released for the original PlayStation. From all-time classics like Final Fantasy VII and Resident Evil 2 to quirky gems like PaRappa the Rapper, the PS1 had it all.
Small Business

The 15 best tech jobs boast top salaries, high satisfaction, lots of openings

The bonanza of tech jobs just keeps coming. High-paying tech jobs abound at companies where people love to work. If you’re ready to make a change, this is a great time to look for something more fulfilling.   
Gaming

The best Nintendo Switch games, from Breath of the Wild to Rocket League

The Nintendo Switch's lineup started off small, but games have steadily released as the console continues through its second year. Here are the best Nintendo Switch games available now.
Gaming

These Xbox One exclusives are the definition of quality over quantity

Xbox One has a prestigious collection of handpicked titles that you can't play on other consoles. Here are the latest and greatest Xbox One exclusives, including some that are also available on PC
Gaming

Law firm files class-action lawsuit over Nintendo Switch Joy-Con drifting issue

A class-action lawsuit has been filed over the Joy-Con drifting issue of the Nintendo Switch. The lawsuit alleges that the joysticks on the Joy-Cons are defective, resulting in the controllers registering movement even without player input.
Gaming

Wage war on a budget with these fun and free first-person shooters

We all know about Halo and Call of Duty by now, but what about quality titles that won't cost you upward of $60? Check out our picks for the best free first-person shooter games from Paladins to Quake Champions.
Gaming

Get Nindie with it and check out these awesome indie games for the Switch

The Nintendo Switch's portability makes indies feel at home on the platform. Luckily, there are plenty of great titles to choose from. Here are our picks for the best Nintendo Switch indie games.
Gaming

Respawn against Apex Legends players using keyboard and mouse on consoles

Respawn said that it does not condone players using keyboard and mouse in Apex Legends on consoles. Some players believe that the alternate input device gives too much of an advantage over players using controllers.
Gaming

Blizzard teases Overwatch hero 31, but name and image may have already leaked

Blizzard teased hero 31 of Overwatch through a faux Developer Update that featured a wormhole and several complicated equations. However, the new character's name and image may have already been leaked.
Gaming

Be forewarned, these free MMORPGs will slay your spare time

Have ample time on your hands and an unquenchable thirst to beat, battle, and blast your way through worlds of fantasy and sci-fi splendor? Check out our picks for the best free MMORPGs.
Buying Guides

The PS4 has great exclusives, but which ones should you get? Here are the best

The PlayStation 4's game library and an incredible selection of exclusive games could make anyone with an Xbox One or Nintendo Switch think twice. Here's our list of the latest and greatest PS4 exclusives.
Gaming

These awesome free-to-play games might be even better than the ones you paid for

Believe it or not, free-to-play games have evolved into engaging, enjoyable experiences. Here are a few of our favorites that you can play right now, including Warframe and the perennially popular League of Legends.