Super Mario is mathier than you think

You control a plumber who jumps and stomps through pipes and monsters to rescue a kidnapped princess. Research from the MIT Hardness Group shows that for some custom Super Mario levels it is impossible to write a computer program that always correctly predicts whether Mario can reach the goal; deciding reachability in those levels is at least as complicated as decoding the encryption behind financial transactions.

The work began in Erik Demaine’s class, Algorithmic Lower Bounds: Fun with Hardness Proofs. Demaine and his collaborators have long studied the computational complexity of games, and a team of four students—Hayashi Ani, Holden Hall, Ricardo Ruiz, and Naveen Venkat—used fan-made level editors and Super Mario Maker to construct levels whose reachability problem is undecidable.

Demaine had thought Mario lived in PSPACE, but the students’ constructions push the game into RE-Complete. “It’s the hardest complexity class we could imagine for these sorts of games,” he says.

super mario, computational complexity, reachability problem, undecidable, re-complete, pspace, erik demaine, mit hardness, mario maker, fan levels