P vs NP: The Million-Dollar Problem That Could Break the Internet
pplpod12 Sep

P vs NP: The Million-Dollar Problem That Could Break the Internet

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!

Is recognizing a brilliant solution fundamentally as easy as finding one? That question, grounded in hard mathematics, is the P versus NP problem, and answering it carries a $1 million bounty from the Clay Mathematics Institute. This episode explains polynomial time, non-deterministic polynomial time, and why a hundred binary choices create a haystack of over a nonillion possibilities that no classical computer could search in the age of the universe.

It walks through NP-completeness and the Cook-Levin theorem, how a university scheduling problem can be reduced to a generalized Sudoku or a 3SAT logic formula, and why solving one of more than 3,000 NP-complete problems quickly would topple all of them. It then lays out the two worlds Russell Impagliazzo described: Cryptomania, where RSA encryption and blockchain hashes survive, and Algorithmica, where protein folding and the traveling salesman problem become easy and, as Scott Aaronson notes, the creative leap loses its special value.

  • Why verifying a path is polynomial while finding it can be exponential
  • Kurt Gödel's 1956 letter to John von Neumann anticipating the question
  • John Nash's 1955 prediction to the NSA that codes would resist shortcuts
  • Why 88 percent of researchers in a 2018 poll believe P does not equal NP
  • How delivery trucks tackle an NP-complete routing problem using heuristics

Denne episoden er hentet fra en åpen RSS-feed og er ikke publisert av Podme. Den kan derfor inneholde annonser.

Episoder(16184)

The Art of Adult Friendship: Why Quality Matters More Than Quantity

The Art of Adult Friendship: Why Quality Matters More Than Quantity

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!In this episode of pplpod, we explore how our understanding of friendship changes as we grow old...

9 Nov 18min

Summer Explained: The Science, History, and Traditions of the Warmest Season

Summer Explained: The Science, History, and Traditions of the Warmest Season

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!In this episode of pplpod, we explore summer, the season most closely associated with sunshine, ...

7 Nov 18min

Sir Patrick Stewart: From Shakespeare to Star Trek, the Life and Legacy of a Legend

Sir Patrick Stewart: From Shakespeare to Star Trek, the Life and Legacy of a Legend

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!In this episode of pplpod, we explore the extraordinary life of Sir Patrick Stewart, the acclaim...

7 Nov 49min

Larry David: The Genius of Social Awkwardness, Seinfeld, and Curb Your Enthusiasm

Larry David: The Genius of Social Awkwardness, Seinfeld, and Curb Your Enthusiasm

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!In this episode of pplpod, we explore the life and career of Larry David, the comedian, writer, ...

6 Nov 38min

Why Australian Shepherds Aren't From Australia

Why Australian Shepherds Aren't From Australia

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!In this episode of pplpod, we explore the history of the Australian Shepherd, an intelligent, en...

5 Nov 45min

Labrador Retriever: From Newfoundland Fishing Dogs to Modern-Day Heroes

Labrador Retriever: From Newfoundland Fishing Dogs to Modern-Day Heroes

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!In this episode of pplpod, we explore the remarkable history of the Labrador Retriever, one of t...

4 Nov 53min

Discovering Ireland: A Journey Through History, Culture, and the Wild Atlantic Way

Discovering Ireland: A Journey Through History, Culture, and the Wild Atlantic Way

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!In this episode of pplpod, we explore Ireland through the philosophy of slow travel: go slower, ...

3 Nov 48min

Willie Hutch: An Overnight I'll Be There Lyric and The Mack's Soundtrack

Willie Hutch: An Overnight I'll Be There Lyric and The Mack's Soundtrack

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!William McKinley Hutchins was born in Los Angeles in December 1944 and raised in Dallas, where h...

2 Nov 21min

Populært innen Underholdning

papaya
enkel-servering
harm-og-hegseth
tore-og-haralds-podkast
storefri-med-mikkel-og-herman
big-5-med-nils-og-harald-2
tusvik-tnne
topp-3-med-wold-og-fladseth
konspirasjonspodden
ma-pa-behandling-med-morten-ramm
hovla
kjendiscrush-med-sofie-karlstad
folk-flest-med-linn-og-nils
gi-meg-alle-detaljene
vitnemal
feedback-med-egon-holstad
rss-gammal-maiden
nare-venner
singel
humorprisen