https://d2r55xnwy6nx47.cloudfront.net/uploads/2024/03/RussellImpagialzzo-byJesseAragon-Lede.V2-scaled.webp
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.