Roughgarden's IAS Course Traces the Line Between What Computers Can and Can't Do

A free lecture course from Tim Roughgarden, now a mathematics professor at the Institute for Advanced Study, walks through the theoretical spine of computer science starting from Turing’s 1936 work — a decade before real computers existed. The starting point is the limit of computation itself: Turing proved that some problems, most famously deciding whether an arbitrary program will ever halt, can never be solved by any algorithm regardless of available time or hardware.

From there the course shifts from what is computable to what is computable quickly. Roughgarden uses familiar wins like Dijkstra’s shortest-path algorithm (behind phone map routing) and Karatsuba’s faster multiplication to show how clever shortcuts beat brute force — then contrasts them with the Traveling Salesman Problem, which looks similar but has resisted every fast algorithm. That contrast opens into NP-completeness, the discovery that thousands of unrelated-looking problems in scheduling, optimization, and puzzle-solving are secretly the same problem: crack one efficiently and they all fall.

The series builds toward P versus NP, still the central open question in the field and one of mathematics’ major unsolved problems, tracing its lineage through Hilbert, Gödel, and von Neumann. Roughgarden closes on the stakes — what an answer either way would mean for cryptography, AI, and quantum computing — and pitches the material to require no prior CS or math background.