If you've ever got stuck playing Super Mario, some good news - it's scientifically difficult to complete.
That's according to a team of computer scientists from MIT's Computer Science and Artificial Intelligence Lab (CSAIL), the University of Ottawa and Bard College.
The team said that solving a level in the classic Nintendo game is "as hard as the hardest problem in the 'complexity class' PSPACE".
This means that completing a level is harder than factoring large numbers, or the Travelling Salesman Problem - a classic algorithmic problem used by AI experts. Typically, 'P' problems are relatively easy to solve, while NP problems are hard for humans to solve without a computer.
"The paper doesn't attempt to establish that any of the levels in commercial versions of Super Mario Brothers are that hard, only that it's possible to construct PSPACE-hard levels from the raw materials of the Super Mario world," the team wrote.
Previous work from the same team has shown Super Mario Brothers is "at least as hard as the hardest problem in NP", but were unable to determine whether it was "any harder".
The team added that computational models and video games could be used to inform ne another. "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," they wrote.
Other games have been used to demonstrate P and NP problems - most notably commuter favourite Candy Crush Saga, which in March 2014 was demonstrated to also be an NP problem.
Back in 2013 a computer scientist even designed an algorithm in an attempt to 'solve' Super Mario Bros and other classic NES games.
"I'm really excited about these kinds of hardness proofs, and I’ve been pushing them a lot in the last couple years,” said 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."
This article was originally published by WIRED UK
