Erik Demaine's Computational Complexity Results for Super Mario Games

This page details the proof techniques and findings from Erik Demaine and colleagues' work on classifying the computational hardness of various Super Mario games. The results hinge on reductions from known hard problems.

Proof Techniques by Target Complexity Class

NP-Hardness Proof

Reduction Source: 3-SAT (A canonical NP-complete problem).

Mechanism: Game elements (platforms, enemies, items) are crafted into logic gadgets that simulate variables and clauses of a 3-SAT formula. A successful path through the level is equivalent to finding a satisfying assignment for the Boolean formula.

Game Examples: Early results for many 2D Mario games established NP-hardness via this route.

PSPACE-Hardness Proof (A Core Contribution)

Reduction Source: A PSPACE-complete "door" problem (e.g., Nondeterministic Constraint Logic).

Mechanism: The research constructs complex, stateful door and switch gadgets. These model problems that require tracking a changing state over time or re-traversing areas, placing the game in the PSPACE class, which is believed to be far more complex than NP.

Game Examples: This technique proved that the original Super Mario Bros. and many other 2D Mario games are PSPACE-complete.

RE-Completeness Proof (Undecidability)

Reduction Source: The Halting Problem (The classic undecidable problem).

Mechanism: Game mechanics are used to simulate a counter machine or a Turing machine within a level. If a Mario level can emulate any computer program, then determining if it is solvable is equivalent to determining if that program halts, making it undecidable.

Game Examples: This strongest-possible result applies to games with powerful creation tools, like Super Mario Maker and the New Super Mario Bros. series.

Summary of Results

Target Hardness Class	Primary Reduction Source	Key In-Game Concept	Implication
NP-Hard	3-SAT	Logic Gadgets	The game is at least as hard as the hardest problems in NP (checking a solution is easy, but finding one is believed to be hard).
PSPACE-Complete	Planar Door / NCL Problem	Stateful Door Gadgets	The game captures problems that require significant memory/planning, a class harder than (or equal to) NP.
RE-Complete (Undecidable)	The Halting Problem	Counter Machine Simulation	No general algorithm can exist to solve all levels of the game. This is the theoretical maximum hardness.

Content synthesized from research publications and presentations by Erik Demaine, Giovanni Viglietta, and colleagues.