Imagine you’re on a quest to understand the very nature of computation. You’re deep in the wilderness, far from any paths, and inscrutable messages are carved into the trunks of trees all around you — BPP, AC0[m], Σ2P, YACC, and hundreds of others. The glyphs are trying to tell you something, but where to begin? You can’t even keep them all straight.
Few researchers have done as much as Russell Impagliazzo to cut through this seeming chaos. For 40 years, Impagliazzo has worked at the forefront of computational complexity theory, the study of the intrinsic difficulty of different problems. The most famous open question in this field, called the P versus NP problem, asks whether many seemingly hard computational problems are actually easy — with the right algorithm. An answer would have far-reaching implications for science and the security of modern cryptography.
In the 1980s and 1990s, Impagliazzo played a leading role in unifying the theoretical foundations of cryptography. In 1995, he articulated the significance of these new developments in an iconic paper that reformulated possible solutions to P versus NP and a handful of related problems in the language of five hypothetical worlds we might inhabit, whimsically dubbed Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania. Impagliazzo’s five worlds have inspired a generation of researchers, and they continue to guide research in the flourishing subfield of meta-complexity.
And these aren’t the only worlds he’s dreamed up. Impagliazzo has been a lifelong aficionado of tabletop role-playing games like Dungeons and Dragons, and he delights in inventing new sets of rules and new settings to explore. The same playful spirit animates his 30-year practice of improvisational comedy.
Impagliazzo also did foundational work elucidating the fundamental role of randomness in computation. In the late 1970s, computer scientists discovered that randomness could sometimes improve algorithms for solving inherently deterministic problems — a counterintuitive finding that perplexed researchers for years. Impagliazzo’s work with the complexity theorist Avi Wigderson and other researchers in the 1990s showed that if certain computational problems really are fundamentally hard, then it’s always possible to convert algorithms that use randomness into deterministic ones. And conversely, proving that randomness can be eliminated from any algorithm would also prove that truly hard problems exist.
Quanta spoke with Impagliazzo about the difference between hard problems and hard puzzles, consulting oracles, and the mathematical lessons of improv comedy. The interview has been condensed and edited for clarity.
