Computation as a Universal and Fundamental Concept

Tim Roughgarden explores fundamental questions about computation's capabilities and limitations, beginning with Alan Turing's 1936 proof that some problems are mathematically unsolvable and progressing to the modern challenge of determining which solvable problems can be solved quickly. He explains how thousands of seemingly different computational problems are actually equivalent versions of the same underlying challenge—a discovery that led to the P versus NP question, computer science's most important unsolved problem with profound implications for cryptography, AI, and quantum computing. The material requires no prior background and examines how two separate research traditions on algorithmic possibilities and limitations converged on this central question.