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