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

Emerging Tech

Inside the Ocean Cleanup’s ambitious plan to rid the ocean of plastic waste

In 2013, Boyan Slat crowdfunded $2.2 million to fund the Ocean Cleanup, a nonprofit organization that builds big, floating trash collectors and sets them out to sea, where they’re designed to autonomously gobble up garbage.
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.
Gaming

The hottest Nintendo Switch games you can get right now

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.
Movies & TV

The best shows on Netflix right now (April 2019)

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

AMD's upcoming Navi graphics cards are incoming. Here's what to expect

AMD's Navi graphics cards could be available as soon as July 2019 — as long as it's not delayed by stock problems. Billed as a successor to Polaris, Navi promises to deliver better performance to consoles like Sony's PlayStation 5.
Computing

Working hard or hardly working? Do it right with these versatile PC desks

Looking for a new piece of furniture that will fit in your office, dorm, or gaming cave? Here are some of our favorite computer desks on the market, whether you're a serious gamer looking for an upgrade, or just moved into a new space.
Gaming

Persona 5 The Royal due in 2020, will introduce new character and story chapter

Details for Persona 5 The Royal, an enhanced re-release of the original game, have been revealed in a new trailer from Atlus. The Royal introduces a new character that joins the Phantom Thieves and improves the overall experience.
Gaming

From the most 'Toasty!' to the least, here are the Mortal Kombat games ranked

The Mortal Kombat franchise has provided shocking delights and spilled copious pints of blood since 1992. With Mortal Kombat 11 out now for PS4, Xbox One, Switch, and PC, we decided to rank the mainline fighting series from best to worst.
Gaming

Collected ’em all? Here are 10 collection-based RPGs Pokémon fans should try

The Pokémon games offer more than 700 monsters to catch and train, sure, but what do you do once you've caught 'em all? These 10 Pokémon-style games will help you find your next fix when need a new set of critters to catch and train.
Gaming

Anthem Act 1 features and content delayed, including Cataclysm world event

The features and events from Act 1 in the Anthem road map are taking a backseat as the developers work on the game's direction while bluntly stating that the online shooter is a long way from being the game they want it to be.
Gaming

15 Nintendo Switch games you should play in handheld mode

The Nintendo Switch's handheld mode is more than a convenient way to play games -- it's also the preferable way for some titles. Here are 15 Nintendo Switch games you should play in handheld mode.
Gaming

These are all the games we want to see from Square Enix at E3 2019

Square Enix will once again hold its own press conference for E3 2019. These are the games we want the company to show during the event, including the long-awaited Final Fantasy VII Remake.
Gaming

Days Gone will receive free post-launch DLC starting in June

Days Gone launches this week and the developers are already setting the stage for post-launch content. Starting in June with the Survivor mode, Bend Studio will begin releasing weekly free updates that include various challenges.
Computing

These gaming monitors will transport you to another dimension

What are the best gaming monitors you can buy right now? We select five that are all priced under $900 packing premium technologies like G-SYNC and FreeSync, high resolutions, and fast refresh rates.