Super Mario Is Mathier Than You Think
You might remember Super Mario Bros. as the game that consumed your childhood afternoons — a cheerful romp through colorful worlds where a plumber in red overalls stomped on mushrooms and rescued a princess. But hidden beneath those pixelated landscapes and bouncing koopa shells lies a problem so mathematically profound that no computer on Earth — or even a hypothetical one — is powerful enough to fully solve it. According to researchers affiliated with MIT, figuring out whether Mario can even complete his quest is at least as complicated as breaking the encryption that protects your online banking transactions.
So the next time someone dismisses video games as mindless entertainment, you have something very interesting to say back.
The Setup: More Than a Plumber's Problem
Here is the scenario. You are an ambitious young plumber from Brooklyn dropped into a world filled with violent, human-sized mushrooms called Goombas. The love of your life has been kidnapped, and your only tools are your ability to jump and stomp. You must navigate pipe-filled, monster-ridden terrain across level after level to reach her.
Simple enough on the surface. But researchers at the MIT Hardness Group have shown that determining whether Mario can actually reach the end of a given level — accounting for all the obstacles, enemies, power-ups, and platforming physics — is a problem that falls into one of the hardest categories in all of computer science. It is not just difficult. It is, in a formal mathematical sense, extraordinarily complex.
Who Is the MIT Hardness Group?
Despite the official-sounding name, the MIT Hardness Group is not a traditional research lab with dedicated funding and office space. It is more of a working title — a collective identity for theoretical computer science projects that emerge from a course taught by Professor Erik Demaine called Algorithmic Lower Bounds: Fun with Hardness Proofs. The group does maintain a YouTube channel, which gives it a slightly more public-facing presence, but at its core it is a community of curious minds tackling some of the deepest questions in the theory of computation.
And yes, several of those questions involve Super Mario.
Erik Demaine: The Genius Behind the Game Theory
Erik Demaine is a professor of computer science at MIT whose academic career reads like a highlight reel. He received a MacArthur Fellowship — commonly referred to as a "genius grant" — for his groundbreaking work in computational geometry, particularly on protein folding and the mathematics of origami. These are fields where the physical world and abstract mathematics intersect in beautiful and practical ways.
But Demaine's interests extend into complexity theory, a branch of computer science focused on classifying problems according to how much time and memory a computer needs to solve them. Complexity theory asks a fundamental question: given a problem, how hard is it — not just in practice, but in principle?
Demaine also happens to be a lifelong Nintendo fan. "I grew up playing NES games," he has said. "I poured many hours into playing as a kid, so it's fun to come back to it these many years later and tie it into my research." That personal history turned into a remarkable intellectual project: using the framework of complexity theory to analyze the mathematics embedded in Super Mario Bros.
What Does "Computational Complexity" Actually Mean?
To understand why Mario's quest is so mathematically significant, it helps to understand what computational complexity theory actually studies. At its core, this field is about categorizing problems based on how efficiently they can be solved. Some problems are easy — a computer can crack them in milliseconds regardless of how large the input gets. Others grow so demanding as inputs scale up that even the fastest supercomputer would need longer than the age of the universe to find a solution.
Problems in the hardest known categories — such as those described as NP-hard or PSPACE-hard — are the ones that matter most to this research. Crucially, many real-world systems rely on the difficulty of these problems for security. The encryption protecting your financial transactions, for example, is built on the assumption that certain mathematical problems are computationally infeasible to reverse. Demonstrating that a problem is "as hard" as those encryption challenges is a formal way of saying it belongs in the same elite tier of difficulty.
The MIT Hardness Group's research demonstrated that Super Mario Bros. belongs in that tier.
Why Video Games Make Great Complexity Puzzles
It might seem strange to use a video game to explore deep mathematical theory, but games are actually ideal for this kind of research. Here is why:
- Games have clearly defined rules, which makes them easy to model mathematically.
- Game levels can be designed or generated in infinite combinations, allowing researchers to construct specific scenarios that mimic other known hard problems.
- The challenge of "can a player get from point A to point B" maps cleanly onto classical questions in graph theory and logic that complexity theorists already study.
- Games are engaging, which makes the research accessible and helps communicate abstract ideas to a broader audience.
Super Mario is particularly rich because its mechanics — running, jumping, enemy interactions, hidden blocks, pipes, power-ups — create a layered system with enormous combinatorial depth. The number of possible states a Mario level can be in grows astronomically as levels get larger or more complex.
The Real-World Implications
So why does this matter beyond being a fascinating intellectual curiosity? Because complexity proofs have real stakes. When researchers demonstrate that a new problem is as hard as a known benchmark problem, they are contributing to a broader map of computational difficulty. That map helps engineers, cryptographers, and scientists understand what kinds of problems can realistically be automated and which ones will always require human judgment or approximation.
It also raises awareness of how deeply mathematical structure is woven into everyday experiences — even ones as familiar as guiding a plumber through a pixelated kingdom. The fact that a game millions of people have played casually sits at the frontier of theoretical computer science is a reminder that mathematics is never far beneath the surface of the world around us.
The Bigger Picture: Math Is Everywhere You Play
The work of Demaine and the MIT Hardness Group is part of a growing tradition of using popular games to illuminate complex ideas. Researchers have studied the computational hardness of Tetris, Minesweeper, Pac-Man, and many others, often arriving at similarly surprising conclusions. These are not trivial exercises. They are rigorous proofs that expand our understanding of what machines can and cannot do.
Super Mario may have started as a simple story of a plumber in love, navigating a world of turtles and mushrooms. But thanks to researchers willing to look beneath the surface, it has become something much more: a window into some of the most profound and unsolved questions in all of mathematics and computer science. The next time you pick up a controller, remember — you might just be playing inside a problem that no computer can solve.