How Algorithms Outsmart Complexity

Tim Roughgarden continues his exploration of computation by revealing how algorithms crack seemingly impossibly large problems with elegant, efficient solutions. The lecture begins with the story of Karatsuba, a 23-year-old who disproved a conjecture by the legendary Kolmogorov, showing that grade school multiplication could be beaten through a simple but brilliant trick: reusing partial results instead of computing them from scratch. Roughgarden walks through the mechanics step by step, demonstrating how splitting numbers and recombining them cleverly saves an entire multiplication at every level of recursion. The lecture then turns to finding shortest paths in networks, where checking every possible route leads to an explosion of options that dwarfs the number of atoms in the universe. Dijkstra's algorithm solves this beautifully, like an expanding balloon finding optimal paths as it grows. The discussion builds toward a profound open question: are there problems that have easy-to-check solutions but nevertheless require brute-force search? This is the essence of the P versus NP question, the deepest unsolved problem in computer science.