If you've ever struggled to solve a level of "Super Mario Bros.," new research from the Massachusetts Institute of Technology will definitely cheer you up. The world of "Super Mario" is definitely mathematically hard.

According to a new paper, which will be presented at the International Conference on Fun with Algorithms next week, the world one can build from the raw materials of "Super Mario" can be as hard as the hardest PSPACE problems.

PSPACE is a complexity class in computer science, grouping problems that have a certain degree of difficulty together. PSPACE is the set of all problems that take a "polynomial" amount of memory space to solve, which depends on the size of the input.

An algorithm that needs to sort out through N numbers to find the largest, for example, would need memory space proportional to N. If we wanted to have a list of the distance between N cities, we would need N^2 space because for every city the algorithm would have to calculate a distance to all the others.

Some problems in PSPACE might be easy to solve, whereas some might be difficult to solve but the solution might be easy to verify. The hardest problems are hard to solve and also hard to verify. You can construct a "Super Mario" level that would take an algorithm both a long time to solve and a similarly long time to navigate even if it had the solution.

“I’m really excited about these kinds of hardness proofs, and I’ve been pushing them a lot in the last couple years,” Erik Demaine, co-author of the paper, said in a statement. 

He added: “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.”

Mathematics doesn't tend to focus on the now, so a solution that might be obtained now, even in video games, might find an important application in years or maybe centuries to come.

^{Top image credit: Super Mario Bros. was released on NES. Carles Escrig i Royo via Flickr CC BY-SA 2.0}