Super Mario is mathier than you think

Here’s a problem you probably didn’t solve in school: You’re an ambitious young plumber from Brooklyn in a world inhabited by violent human-size mushrooms called Goombas. The love of your life has been kidnapped, so you embark on a quest to rescue her, venturing through stretches of pipe-filled and monster-­ridden terrain where your only means of protection are your powers of jumping and stomping. It’s a journey so arduous that no computer—real or hypothetical—is powerful enough to figure out if you can reach her. And according to research published by the MIT Hardness Group, determining whether your quest is possible at all is at least as complicated as decoding the encryption behind financial transactions. But if this problem could talk, the first thing it would say is “Hello, it’s a-me, Mario!” For the love of the game Though it does have a YouTube channel, the MIT Hardness Group isn’t an official research group. Instead, it’s a placeholder name for theoretical computer science projects—including several related to Super Mario—from Erik Demaine’s class Algorithmic Lower Bounds: Fun with Hardness Proofs. Demaine, a professor of computer science, received a MacArthur fellowship (also known as a “genius” grant) for his work in computational geometry on protein folding and origami. But he also researches complexity theory, which focuses on organizing problems into categories based on how much time and memory space it takes for computers to solve them. He happens to be an avid Super Mario fan as well. “I grew up playing NES [Nintendo Entertainment System] games,” Demaine says. “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.” Erik Demaine researches complexity theory, which examines the amount of time and memory that computers need to solve problems. He’s also an avid Super Mario fan.DONNA COVENEY/MIT Super Mario takes place on a horizontally scrolling universe of platforms, pipes, and other