Cryptography's Mathematical 'Worlds': Which One Do We Live In?

For forty years, Russell 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 1995, Impagliazzo wrote a seminal paper where he reformulated possible solutions to P versus NP 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 CINEMATOGRPAHY: Jesse Aragon ---------- Read the full article for links to papers: https://www.quantamagazine.org/the-researcher-who-explores-computation-by-conjuring-new-worlds-20240327/ Read the Quanta article about Impagliazzo's Five Worlds - Which Computational Universe Do We Live In? https://www.quantamagazine.org/which-computational-universe-do-we-live-in-20220418/ ---------- Chapters: 00:00 Cryptography is the killer app of Computational Complexity 01:31 Impagliazzo's Five Worlds 02:03 World 1 - Algorithmica 02:27 World 2 - Heuristica 02:53 World 3 - Pessiland 03:15 World 4 - Minicrypt 03:52 World 5 - Cryptomania - cryptography as we know it ---------- - VISIT our website: https://www.quantamagazine.org - LIKE us on Facebook: https://www.facebook.com/QuantaNews - FOLLOW us Twitter: https://twitter.com/QuantaMagazine Quanta Magazine is an editorially independent publication supported by the Simons Foundation: https://www.simonsfoundation.org/