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/