Two Worlds We Might Live In

Tim Roughgarden dives into the P versus NP question, widely considered the most important open problem in computer science. Building on earlier groundwork about easy and hard problems, he traces the historical origins of NP-completeness, from Karp's landmark list of 21 problems to the pioneers who shaped the field. Roughgarden highlights two threads of research: the more engineering-oriented pursuit of efficient algorithms, and the more mathematically focused quest for lower bounds and impossibility results, that converged on the P versus NP question. He lays out the two possible worlds: one where P equals NP and what were thought to be hard problems can actually be solved quickly, and one where they cannot. He examines why most experts bet that P does not equal NP, considers the intuitive "vibes argument" for this belief, and confronts the sobering reality that proving it may be nearly impossible. The episode sets the stage for a final installment on the real-world ramifications of either answer.