Computation as a Universal and Fundamental Concept

Tim Roughgarden begins with a deceptively simple question: is there anything computers cannot do? To answer it, he takes us back to 1936, when Alan Turing, a decade before actual computers existed, laid the foundations of computer science as a byproduct of solving an obscure mathematical problem. Turing's paper introduced the theoretical machine that bears his name and proved something startling: there are problems no algorithm can ever solve, no matter how much time or computing power we throw at them. The halting problem, which asks whether a program will eventually stop running, is forever beyond the reach of any computer.

From this foundation, Roughgarden pivots to a more subtle question. Among the problems computers can solve, which ones can they solve quickly? He introduces us to algorithmic shortcuts, clever tricks that let programs avoid examining every possible solution. Your phone's map application builds on Dijkstra's algorithm to find the shortest route without checking every conceivable path. Karatsuba's multiplication method beats the grade-school approach we all learned. These shortcuts seem almost magical, and they raise a natural hope: perhaps such shortcuts exist for every problem.

That hope crashes against the Traveling Salesman Problem. Despite looking nearly identical to shortest-path routing, TSP has resisted every attempt to find a fast algorithm. Roughgarden explains how this puzzle led to the theory of NP-completeness, one of computer science's most surprising discoveries. Thousands of seemingly unrelated problems (scheduling, puzzle-solving, network optimization) turn out to be disguised versions of the same underlying challenge. If anyone finds a fast algorithm for any one of them, all become easy. If any one is truly hard, all are hard.

This brings us to P versus NP, the most important open question in computer science and one of the great unsolved problems in mathematics. Roughgarden traces its history through figures like Hilbert, Gödel, and von Neumann, showing how two separate research traditions, one focused on what algorithms can achieve, the other on their limitations, converged on this single question. The course concludes by examining what the answer might mean for cryptography, artificial intelligence, quantum computing, and our understanding of computation itself. No prior background in computer science or mathematics is required.

You can watch the lectures below, browse the chapter index, or watch on YouTube.