Interview, Podcast
Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
- Richard Karp received the 1985 Turing Award for foundational work in theoretical computer science, including the development of:
- The Edmonds-Karp algorithm for solving the maximum flow problem on networks.
- The Hopcroft-Karp algorithm for finding maximum cardinality matchings in bipartite graphs.
- A landmark 1972 paper proving 21 fundamental combinatorial problems to be NP-complete.
- Karp's early mathematical inspiration came from plane geometry, specifically the elegance of proving facts like the sum of triangle angles equals 180 degrees through pure reasoning rather than arithmetic.
- Karp rejects the idea that human-level intelligence or consciousness can be achieved by simply scaling current computational power:
- He believes current AI achievements (speech, robotics, NLP) do not approach the cognitive complexity of a six-month-old child.
- He argues that exponential hardware improvements (Moore's Law) will not bridge the gap until we understand the organizational principles of neural networks.
- He expresses doubt regarding the "singularity" and the existential threat of superintelligent AI surpassing humanity.
- Karp defines "P" as the class of problems solvable in polynomial time (efficient algorithms) and "NP" as problems where a proposed solution can be verified in polynomial time.
- The central open question in computer science is whether P equals NP.
- Karp states he bets that P is unequal to NP.
- If P ≠ NP, it implies that many important combinatorial problems (e.g., factoring large numbers) cannot be solved efficiently, even though their solutions are easy to verify.
- Stephen Cook's 1971 proof that the Boolean Satisfiability Problem (SAT) is NP-complete established the concept of NP-completeness.
- Karp extended this by proving 21 other problems (including integer programming and graph problems) are also NP-complete.
- This proved that all these problems share the same expressive power; if any single NP-complete problem is solvable in polynomial time, then P = NP.
- Karp discusses the "Stable Matching Problem" (Gale-Shapley algorithm) as a particularly beautiful combinatorial algorithm:
- The algorithm guarantees a stable one-to-one matching where no two participants prefer each other over their assigned partners.
- The algorithm involves a "proposing" side and a "reacting" side; the proposing side (boys/men) achieves the best possible outcome in any stable matching.
- Adding real-world constraints (e.g., couples wanting to be assigned to the same location) transforms the problem from polynomial-time solvable to NP-hard.
- Karp developed the Rabin-Karp algorithm for string matching, which utilizes randomization:
- The algorithm uses "fingerprinting" (hashing) of substrings by taking remainders modulo a randomly chosen prime number.
- Randomization allows the algorithm to run extremely fast with a low probability of error, which can be verified subsequently.
- Theoretical computer science traditionally relies on worst-case analysis, which Karp argues is sometimes misleading:
- He notes that SAT solvers and algorithms for the Traveling Salesman Problem often perform exceptionally well in practice on real-world instances, despite their NP-hard classification in the worst case.
- "Average-case" or probabilistic analysis is difficult because defining a representative "typical" problem space is non-trivial.
- Karp observes that the machine learning field differs significantly from theoretical computer science:
- Machine learning results are often empirical rather than theoretically grounded in algorithmic guarantees.
- Neural networks function as complex, unexplainable functions; while they perform well, there is little insight into the specific features they learn or why they generalize to unseen data.
- Karp views bioinformatics and genetic engineering (e.g., CRISPR) as areas where algorithms can solve massive data problems but raises serious ethical concerns:
- Editing germline DNA poses risks due to unknown side effects and ethical hubris.
- Algorithmic analysis can help model genomic data to predict disease tendencies and personalize medicine.
- Karp attributes his successful career and teaching style to his father, a geometry teacher who drew perfect circles by hand.
- His advice for effective teaching is "preparation, preparation, and preparation," which allows a teacher to adapt flexibly to student needs in the moment.
- Karp's pivotal career moment occurred during a graduate-level course on operations research, where he outperformed his peers, confirming his potential for research in mathematical methods.