Lex Fridman PodcastRichard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
CHAPTERS
- 0:00 – 3:31
Richard Karp’s legacy: max-flow, matchings, and NP-completeness
Lex introduces Richard Karp’s foundational contributions to algorithms and complexity theory, from max-flow and bipartite matching to NP-completeness. He frames Karp’s 1971 paper as a catalyst for the modern study of P vs NP.
- •Karp’s major algorithms: Edmonds–Karp, Hopcroft–Karp, Rabin–Karp
- •The 1971 paper establishing 21 NP-complete problems
- •Why NP-completeness reshaped theoretical CS
- •Context: Turing Award and impact on algorithm theory
- 3:31 – 8:34
Plane geometry and the joy of ironclad proof
Karp recalls being captivated as a teenager by the elegance and certainty of geometric reasoning. He and Lex unpack simple but powerful proofs, including shortest distance arguments and the triangle-angle-sum theorem.
- •Story about shortest distance between two circles via centers
- •Why formal proof feels “beyond dispute”
- •Geometry as puzzle-solving vs rote arithmetic
- •Triangle angles sum to 180° proof idea (parallel line/alternate angles)
- 8:34 – 13:00
Visualization vs algebra: how Karp thinks about math and algorithms
Lex asks what Karp ‘sees’ when designing algorithms. Karp describes iterative progress—inner loops that monotonically reduce a gap to optimality—and notes he relies more on algebra than high-dimensional geometric intuition.
- •Algorithms as repeated inner loops that converge to a solution
- •Visualizing progress as decreasing distance to optimum
- •Example intuition from experimenting on Traveling Salesman–type objectives
- •High-dimensional geometry is motivating, but algebra drives his reasoning
- 13:00 – 18:28
The Hungarian algorithm and the aesthetics of computation (being a ‘geek’)
Karp explains the assignment problem and the Hungarian algorithm’s iterative structure. He describes why such systematic transformations feel beautiful and how this connects to Knuth’s idea of ‘geeks’ enjoying computational process structure.
- •Assignment problem: minimum-cost one-to-one matching in a cost matrix
- •Key invariant: subtracting constants from rows/columns preserves optimal assignment
- •Iteratively modifying the matrix to create a zero-permutation indicating optimality
- •Aesthetic appeal: orderly, step-by-step shaping toward a solution
- 18:28 – 25:06
Early fascination with numbers and early computers at Harvard
Karp reflects on mental arithmetic habits and anecdotes from early jobs, then shifts to the physical reality of 1950s computers. He describes Harvard’s Mark IV and early UNIVAC constraints, especially memory and data access limitations.
- •Playing with numbers: mental multiplication and doubling for memory
- •Anecdote: working as a Skee-Ball barker and impressing coworkers with arithmetic
- •Mark IV room-sized machine, relays, and literal ‘bugs’
- •UNIVAC with 2,000 words of storage and the ‘art’ of memory layout
- 25:06 – 33:23
Turing Test skepticism, human intelligence, and consciousness
Lex and Karp discuss whether machines can reach human-level intelligence. Karp criticizes the Turing Test as subjective, doubts current AI approaches capture human cognition, and notes how consciousness resists rigorous definition.
- •Turing Test viewed as too subjective for calibrating intelligence
- •Human cognition involves changing environments, embodiment, emotions, desires
- •Speedups alone (Moore’s Law) won’t solve ‘organization principle’ gaps
- •Consciousness/self-knowledge is hard to define rigorously
- 33:23 – 40:20
What combinatorial algorithms are: graphs, networks, and flows
Karp defines combinatorial algorithms as methods for discrete structures and optimization/existence questions. He introduces graphs, examples from scheduling and circuits, and highlights network flow as a central modeling tool with broad applications.
- •Combinatorial algorithms: discrete objects, discrete states, optimizing costs or proving existence
- •Graph definition and examples: circuits, communities, road networks, scheduling constraints
- •Network flow framing: commodities with capacities on edges
- •Applications: communication, supply chains, transportation, and optimization
- 40:20 – 44:07
Polynomial time and why worst-case complexity matters
Karp formalizes algorithmic complexity, focusing on worst-case step counts as input scales. He explains why polynomial-time is the theoretical notion of ‘efficient,’ while acknowledging practical importance of low-degree polynomials and near-linear time.
- •Polynomial time: steps bounded by a fixed power of input size
- •P as the class of problems solvable in polynomial time (worst-case)
- •Practical vs theoretical efficiency (e.g., n^10000 is ‘poly’ but useless)
- •Large-scale data makes n log n and near-linear methods critical
- 44:07 – 54:25
NP, verification vs solving, and the leap to P vs NP
Karp explains NP as problems whose solutions can be verified quickly even if finding them seems hard. Using clique and scheduling as intuition, he positions P vs NP as the central question about whether verification implies efficient solvability.
- •NP: solutions verifiable in polynomial time
- •Example: clique is hard to find, easy to verify once given
- •P ⊆ NP is clear; NP ⊆ P is unknown
- •Framing of P vs NP and why most believe P ≠ NP
- 54:25 – 1:02:27
Cook’s SAT theorem and Karp’s NP-completeness reductions
Karp explains Cook’s result that SAT is universal for NP via reductions and Turing machine encodings. He then describes his motivation to reduce SAT to many other natural problems, establishing a web of equivalences among classic combinatorial tasks.
- •SAT: assigning truth values to satisfy a Boolean formula
- •Cook’s theorem: every NP problem reduces to SAT
- •Turing machines as a uniform model enabling the reduction
- •Karp’s 1971 program: reducing SAT to 21 fundamental combinatorial problems
- 1:02:27 – 1:09:05
How reductions work: SAT to graph problems (clique/independent set)
Karp walks through the structure of a SAT instance as clauses and literals, and shows how to encode constraints into a graph. The construction ensures choosing compatible literals corresponds to satisfying all clauses, illustrating the ‘expressive power’ shared across problems.
- •CNF view: conjunction of clauses, each an OR of literals
- •Need to pick one true literal per clause without contradictions
- •Graph construction: vertices as literal occurrences; edges forbid incompatible choices
- •Independent set/clique duality as a vehicle for NP-completeness
- 1:09:05 – 1:12:57
NP-complete vs NP-hard, and what a proof of P=NP might require
Karp distinguishes decision problems (NP-complete) from optimization problems (NP-hard). He argues that either outcome of P vs NP would be world-changing and predicts any proof will require fundamentally new concepts beyond current complexity tools.
- •NP-complete applies to decision (yes/no) versions
- •NP-hard often refers to optimization versions
- •Impact if P ≠ NP: rely on heuristics/approximation; optimality can’t be guaranteed always
- •Any P=NP or P≠NP proof likely needs outside-the-box concepts
- 1:12:57 – 1:20:32
Beautiful algorithms: stable marriage and incentives in matching markets
Asked for a favorite elegant algorithm, Karp highlights Gale–Shapley stable matching. He explains stability, the proposal process, why it terminates, and the surprising asymmetry: proposers (boys) do best among stable matchings; adding real-world constraints can make it NP-hard.
- •Stable matching: no pair prefers each other over current partners
- •Gale–Shapley algorithm: proposals, tentative acceptance, upgrades
- •Guarantee of existence and convergence to a stable matching
- •Proposer advantage and real-world complication (couples matching) leading to hardness
- 1:20:32 – 1:33:22
Randomized algorithms and Rabin–Karp fingerprinting
Karp describes the Rabin–Karp string-search algorithm as a showcase for randomization. By hashing substrings using modulo a random prime, the method enables fast rolling updates and low collision probability, with errors checkable after the fact.
- •Problem: find a pattern inside a long string
- •Fingerprint via interpreting as a number and taking mod a random prime (hashing)
- •Rolling hash enables O(1)-ish update while sliding the window
- •Randomness makes collisions unlikely; verification handles rare false matches
- 1:33:22 – 1:43:57
Hard in theory, easy in practice: SAT solvers, TSP, and the limits of average-case theory
Karp argues worst-case guarantees are valuable, but bad worst-case doesn’t doom practical usefulness. He cites modern SAT solvers and large-scale TSP solved via integer programming; he then explains why average-case analysis is hard—‘typical instance’ distributions are unclear—and why early random-graph success felt too toy-like.
- •Worst-case is decisive when it guarantees always-good performance
- •But many NP-complete tasks are tractable on real instances (SAT solvers in industry)
- •TSP: provably optimal solutions for large geometric instances using IP and tricks
- •Average-case analysis challenge: choosing a representative input distribution
- 1:43:57 – 1:50:50
A strange idea in complexity: non-uniform circuits and hierarchy collapse
Karp discusses a 1979 result with Lipton about ‘small circuits’ for NP problems at each input size. They show that if NP had polynomial-size circuits, higher levels of the polynomial hierarchy would collapse—an outcome viewed as implausible and thus indirect evidence against such circuits.
- •Non-uniform complexity: different circuit for each input size n
- •Question: can NP problems have small circuits even if P ≠ NP?
- •Quantifier alternation defines levels of the polynomial hierarchy
- •Result: small circuits for NP would collapse the hierarchy to level 2
- 1:50:50 – 1:56:28
Machine learning vs theory: empirical success and lack of understanding
Karp contrasts theoretical CS’s proof-driven culture with ML’s empirical evaluation. He credits major ML successes but emphasizes limited theoretical explanation for generalization and the opacity of neural-network ‘circuits,’ raising questions about interpretability and scientific insight.
- •ML progress is driven by empirical benchmarks and observed performance
- •Successes: vision, robotics, game-playing (NLP noted as harder historically)
- •Open gap: why generalization works so well without strong theory
- •Neural networks as computable functions/circuits that are hard to interpret
- 1:56:28 – 2:00:37
Bioinformatics, gene editing, and algorithms for genomic big data
Karp reflects on the amazement of DNA as an information substrate and the power of gene editing, alongside ethical concerns (especially germline edits). He then outlines algorithmic opportunities in analyzing genomic and proteomic data for disease risk and personalized medicine.
- •DNA editing’s promise and the ethical divide: somatic vs germline changes
- •Risk of unintended side effects and overconfidence in gene ‘knockouts’
- •Bioinformatics as statistical/big-data computation on genomes and proteins
- •Applications: disease predisposition, ancestry, personalized treatment
- 2:00:37 – 2:05:09
Remembering his father and the craft of teaching
Karp shares a vivid memory of his father teaching—drawing perfect circles and engaging students—and connects it to his own identity as an educator. He stresses that great teaching is built on preparation that enables flexibility, responsiveness, and mentorship tailored to each student.
- •Father as inspirational teacher; classroom as where he ‘came to life’
- •Karp’s pride in teaching legacy as reflected by former students
- •Advice: preparation, preparation, preparation; enables adaptability
- •Mentoring is individualized: different students need different kinds of support
- 2:05:09 – 2:07:32
A personal turning point: discovering his research ability
In closing, Karp recalls being a ‘lazy’ student until research and a standout course performance revealed his capabilities to faculty and to himself. The moment marks a shift toward confidence and a sense of direction that shaped his career.
- •Early lack of motivation as undergrad/early grad student
- •Summer research contributions as a catalyst
- •A standout operations research/math methods course performance
- •Realization of personal ability and trajectory
