A few weeks ago I was listening to one of my favorite radio shows, BBC Radio 4’s In Our Time. It’s about as adult-contemporary as a podcast gets: a roundtable of British academics talking about one subject every week, everything from the Lancashire Cotton Famine to Beowulf to Dark Matter.
Last month they covered a famous math question, the P vs. NP problem. It’s an arcane problem, though famous enough that it turns up as a Simpsons joke. And its implications are genuinely immense.
What is P vs. NP? While it’s one of the hardest unsolved problems in math, it’s conceptually very simple. Start with Wikipedia’s definition of the problem: “Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.”