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