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:

Read the Quanta article about Impagliazzo's Five Worlds - Which Computational Universe Do We Live In?

----------
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
----------

[gubgubbubbub]

I had him as a professor last quarter! Good-natured and wicked smart – solved a problem I'd been struggling with for weeks in a few minutes...

[LeelandOC]

I love content like this. I don't know how else I would connect (even briefly) with the lives of so many people who are slowly advancing the boundaries of human shared knowledge.

[Mattapple]

I feel addicted to mathematics. When I was in grad school, I studied Theoretical CS and wrote my thesis on cryptography (zero-knowledge). Ever since getting out of academia, I spend my free time reading and self studying the math I never got a chance to formally learn like abstract algebra and quantum physics. But then I see a video like this that convinces me I need to spend the next year just going full send on complexity theory and cryptography. 😢 I just dont know if there's enough time in life to learn all the things I want to learn.

[tuams]

I'm happy you are putting out more content. Such good information to learn about the boundaries of our understanding! Thank you.

[ai_outline]

Everything about Computer Science fascinates me so much… I truly love this science ❤️

[Simon-irmq]

Randomly came across the paper some months ago. Was a great read! Nice to see quanta cover it!

[morkovija]

that house on top of a building was super cute and awesome!

[massimopiemontese]

Really good, but why is the music louder than his voice?

[gregyoung]

This is terrific. I can't wait to see where the sixth world takes us. Quanta is the most informative platform i have been able to find for science explanations that are easily understood.

[joshuacarlisle]

Love this guys whole vibe. Adorable yet genius

[cobana]

did not expect to see Geisel in my YouTube feed

[Patashu]

Ooh, there's a sixth world now? That made my day! I wanna learn about it lmao

[NicholasHay]

Going to school at UCSD really is a like attending Lewis Carroll's Wonderland

[forTodaysAdventure]

imagine a traveling salesman problem, but you dont care about getting the fastest path, you just pick a path and go. now that distance that you travelled is your "key". no one else knows the lock because it would be too difficult to check all of the paths to find your particular path. but if you give someone your path, then they can check that you are the owner of the path because it will add up to the distance you also gave them "the key"

[MathFromAlphaToOmega]

I'm certainly not an expert on cryptography, but it seems like much of it depends on P=NP being false. Is there a plan for how to "fix" things if P=NP turns out to be true?

[sushantap]

Is 4:09 where the happy professor lives? : )

[kautzz]

I'm curious what are the three longstanding encryption methods? Is he talking about asymmetric, symmetric and ... hashing? I learned a long time ago that hashing is not encryption. Am I wrong?

[existenceisillusion]

We're just not going to talk about that house 4:07 and 4:09?

[notsojharedtroll]

I'm a simple man, I see the UCSD's Geisel Library and I like

[rajivkrishnakumar]

Wouldn't QKD still be a viable form of cryptography in 'algorithmica' or am I misunderstanding something?