Karp, Richard
▶ Watch on YouTubeCore ideas
Karp traces his love of computer science back to plane geometry at age 13, describing the specific pleasure of "pure reasoning" establishing facts beyond dispute (e.g., proving the shortest path between two circles, or that a triangle's angles sum to 180°), and contrasts this with his lack of three-dimensional visual intuition, which pushed him toward algebraic rather than geometric thinking even in later work on linear and integer programming. He describes the mental experience of designing algorithms as visualizing iterative convergence toward an optimum, illustrated by his early fascination with the Hungarian algorithm for the assignment problem (matching, say, boys to girls to minimize total cost by repeatedly subtracting constants from matrix rows/columns while preserving non-negativity) — an elegance he compares to the satisfaction of skilled craftsmanship. Reflecting on Don Knuth's notion of "geeks" who derive aesthetic pleasure from computational structure, Karp recounts childhood habits (mentally multiplying four-digit numbers, doubling numbers as long as possible before sleep) and suggests such people may function unusually well in worlds of pure abstraction partly because they don't need to master the complexities of human emotional interaction.
On artificial intelligence, Karp — drawing on decades-old skepticism dating to his early exposure to Turing's paper, which he found too subjective as a test — expresses strong doubt that human-level general intelligence is achievable by current approaches, arguing no existing AI system approaches even a six-month-old child's comprehension of the world, and that merely scaling switch speed by orders of magnitude won't help "until we really understand the organizational principle behind the network of switches." He is similarly skeptical of neural networks' theoretical grounding despite acknowledging their empirical successes in vision, robotics, and language: we lack a theory for why they generalize outside their training distribution, and their internal representations remain largely uninterpretable — a limitation he compares to the interpretability gap in his own probabilistic algorithms research, where practitioners rely on empirical performance without full theoretical understanding (as with modern SAT solvers, which handle real-world instances with millions of variables efficiently despite satisfiability being NP-complete in the worst case).
A large technical core of the conversation walks through complexity theory fundamentals: polynomial-time (P) algorithms, whose worst-case running time is bounded by a fixed power of input size; NP, the class of problems whose solutions (though possibly hard to find) can be verified quickly (illustrated via the clique problem — finding a clique is hard, but checking a candidate clique is easy); and NP-completeness. He explains Stephen Cook's 1971 theorem showing the Boolean satisfiability problem is "universal" for NP (every NP problem can be translated into it via Turing machines), and describes his own landmark contribution — the 1972 paper "Reducibility Among Combinatorial Problems" — which showed 21 further problems (including integer programming, clique, and independent set) share this universal expressive power, meaning either all of them or none admit polynomial-time solutions. Karp states his own strong intuition that P ≠ NP, based on centuries of unsuccessful attempts to efficiently solve problems like integer factorization, and describes his 1979 work with Richard Lipton showing that if NP problems had polynomial-size Boolean circuits (a weaker condition than P=NP), an entire polynomial hierarchy of complexity classes would "collapse" — treated as further (though not conclusive) evidence against P=NP. He also highlights randomized algorithms as a favorite personal area, especially the Rabin–Karp string-matching algorithm (using numerical "fingerprints" via modular hashing to detect substring matches efficiently, with small controllable error probability) and randomized primality testing via Fermat's Little Theorem, framing randomization's power as rooted in ordinary statistical sampling intuition (as in polling an election).
Karp singles out the Gale–Shapley stable matching algorithm (matching "boys" and "girls," or medical residents and hospitals, by mutual preference so no pair would rather elope together) as his favorite algorithm not of his own devising, noting the elegant result that the proposing side always does at least as well as in any other stable matching — and that adding real-world constraints (like a married couple needing hospital placements in the same city) can push the problem into NP-hardness. On the gap between theory and practice, he discusses how worst-case complexity classifications (like NP-hardness for the traveling salesman problem) can coexist with excellent real-world performance via heuristics and integer-programming tricks solving instances with tens of thousands of cities, and laments that theoretical computer science has never developed anything like machine learning's shared benchmark datasets — his own attempts at average-case analysis using simplistic random-graph models produced elegant results the field considered insufficiently connected to real-world problem distributions. He closes on gene editing (calling CRISPR-style capabilities "amazing" but ethically fraught, especially for germline modification) and on teaching, crediting his father (a schoolteacher he dedicated his 1985 Turing Award lecture to) as his model, and naming thorough preparation as the single most important ingredient of good teaching because it frees a teacher to adapt in real time to what students actually need.
Excerpts
On the moment he realized Cook's theorem implied a universal structure across combinatorial problems:
“When I saw Cook's paper and saw this reduction of all of each of the problems in NP by a uniform method to the satisfiability problem of propositional logic, that meant that the satisfiability problem was a universal combinatorial problem... it occurred to me, through experience I had had in trying to solve other combinatorial problems, that there were many other problems which seemed to have that universal structure.”
On why he doubts P equals NP:
“There are problems that have been around for centuries and have been studied intensively in mathematics... and no polynomial time algorithms have been found for these easy-to-check problems. One example is a problem that goes back to the mathematician Gauss, who is interested in factoring large numbers... the problem of factoring very large numbers does not appear to have an efficient solution, but once you have found the factors, you can quickly verify that they are factors of the number.”
On why worst-case failure shouldn't mean discarding an algorithm:
“If worst-case analysis is used to show that the solution is not always good, then you have to step back and do something else, to ask how often will you get a good solution... a good example is, going back to the satisfiability problem, there are very powerful programs called SAT solvers which in practice fairly reliably solve instances with many millions of variables that arise in digital design or proving programs correct.”