Super Mario Brothers—the iconic Nintendo video game that spearheaded the 1985 home console revolution—is hard. Objectively, mathematically, scientifically hard. This is one of the key findings of a new paper due to be presented at the International Conference on Fun with Algorithms in La Maddalena Italy.

The study compares Super Mario Bros to PSPACE puzzles, widely considered the most challenging algorithms in computational complexity theory, because they can theoretically take forever to solve and forever to verify. Designating Super Mario Bros as PSPACE-hard puts Nintendo's fiendishly complex levels in company with forms of Boolean algebra, Lambda calculus and, alas, checkers.

"I'm really excited about these kinds of hardness proofs," coauthor Erik Demaine, professor of electrical engineering and computer science at MIT, said in a press statement. "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."