Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111

In this episode, Lex Fridman sits down with Richard Karp, one of the towering figures in theoretical computer science and a Turing Award recipient. The conversation traverses the landscape of algorithms, computational complexity, and the deep mathematical questions that have shaped computer science over decades.

Karp begins by reflecting on the aesthetic dimensions of his work, discussing how geometry and visualization serve as powerful tools for understanding algorithms. He emphasizes the importance of being able to see and comprehend algorithmic processes intuitively, not just understand them mathematically. This theme of elegance in algorithms runs throughout the conversation, with Karp highlighting how beautiful solutions often emerge from deep mathematical insight.

The episode delves into Karp's most significant contributions to computer science. He discusses the Edmonds-Karp algorithm for solving maximum flow problems on networks, explaining how this work connected practical engineering concerns with elegant mathematical theory. More significantly, Karp explores his landmark 1972 paper on reducibility among combinatorial problems, in which he proved 21 different problems to be NP-complete. This work fundamentally shaped how computer scientists think about computational difficulty and became the catalyst for decades of research into the P versus NP problem.

A substantial portion of the conversation focuses on the P equals NP question, arguably the most important unsolved problem in computer science. Karp explains the implications of this problem, the difficulty in approaching it, and why despite its theoretical importance, solving it remains elusive. He discusses NP-complete problems and the stable marriage problem, illustrating how seemingly simple combinatorial questions can have surprising depth and difficulty.

The discussion ventures into practical complexity theory, exploring how problems that are theoretically hard can sometimes be solved efficiently in practice. Karp discusses randomized algorithms and heuristic approaches that work well despite lacking worst-case guarantees. This bridges the gap between worst-case theoretical complexity and the empirical reality of computation.

Toward the episode's conclusion, Karp reflects on open problems in theoretical computer science and shares perspectives on emerging areas like machine learning. He considers how classical complexity theory relates to modern AI and deep learning, suggesting connections between traditional algorithmic thinking and contemporary machine learning approaches. The conversation also touches on consciousness and the nature of computation, with Karp offering philosophical perspectives on these profound questions.

Throughout the episode, Karp demonstrates why he earned his reputation as a foundational thinker in computer science. His ability to connect practical problems to deep theoretical questions, combined with his emphasis on mathematical beauty and elegance, provides a masterclass in computational thinking for both specialists and those new to these ideas.