Richard Karp — Berkeley professor and 1985 Turing Award winner, one of the founding figures of theoretical computer science, known for the Edmonds-Karp max-flow algorithm, the Hopcroft-Karp matching algorithm, the Rabin-Karp string search, and his landmark paper proving 21 problems NP-complete.
The gist
Richard Karp recounts his lifelong love of mathematical elegance, from plane geometry as a teenager to the Hungarian algorithm that revealed him to be a 'geek.' He explains foundational concepts in computational complexity in plain terms: graphs, polynomial time, the classes P, NP, NP-complete, and NP-hard, and how his 1971 reductions tied 21 combinatorial problems together. He discusses randomized algorithms like Rabin-Karp, the limits of worst-case versus average-case analysis, why SAT solvers and traveling-salesman codes work well in practice despite hardness, and his skepticism about human-level AI. He closes on bioinformatics, the ethics of gene editing, and his father's influence on his identity as a teacher.
Big reveals
- Karp bets P is unequal to NP, citing centuries-old problems with no efficient solution found.
- He is doubtful machines will ever achieve human-level intelligence or that the singularity will come.
- Claims no computer program surpasses a six-month-old child in comprehension of the world.
- Argues no constant-factor speedup, even a million-fold, helps until we understand the organizing principle of cognition.
- Explains Cook's result that all of NP collapses to the satisfiability problem, calling its implications staggering.
- Notes practitioners treat NP-complete SAT as 'easy' because real-world solvers reliably handle millions of variables.
- Admits his own random-graph average-case work lacked 'bite' for practical application, a field-defining self-critique.
Things worth remembering
- As a kid Karp put himself to sleep by repeatedly doubling numbers and multiplied four-digit numbers in his head.
- He worked a summer job as a barker at a skee-ball game and impressed coworkers with mental arithmetic.
- As a PhD student in 1955 he joined Harvard's lab where the Mark IV computer filled a room you could walk inside.
- Early computer 'bugs' were literally flying creatures landing on the relay switches.
- The stable marriage problem always has a stable matching, and the proposing side ends up best off.
- Rabin-Karp fingerprints a word as a number mod a random prime, enabling fast sliding-window string search.
- Fermat's little theorem gives a fast randomized proof that a number is not prime.
- Karp's fondest memory of his father is watching him draw perfect circles by hand on the blackboard.
- His top three pieces of teaching advice are 'preparation, preparation, and preparation.'