Richard Karp: Either All These Problems Are Easy, or None of Them Are

Lex Fridman opens with a line Karp himself wrote: at 13 he was first exposed to plane geometry and was wonder-struck by the power and elegance of formal proofs. Karp answers with a story he heard from Michael Rabin. As a boy Rabin was thrown out of class for misbehavior, wandered the corridors, and found two older students stuck on a question: what is the shortest distance between two non-overlapping circles?

Rabin said: take the line of centers; the segment between the two circles is the shortest. Any other segment joining the circles, extended by a radius on each side, becomes a three-edge path between the centers, and a three-edge path cannot beat a straight line. Karp thought, and Rabin thought, that this was just elegant — that pure reasoning could establish a geometric fact beyond dispute. The same pleasure attaches to the theorem that the angles of a triangle sum to 180 degrees. Draw a line through one vertex parallel to the opposite side; alternate interior angles give you a half-plane. The surprise, Karp says, is not that the proof is hard. It is that it is so easy, and yet so convincing.

The visual part of geometry mattered, even though his three-dimensional vision is poor. He cannot picture surfaces and hyperplanes well, which later mattered when linear and integer programming asked him to imagine the highest point on a polyhedron. The picture is motivating. The tool is algebra. Euclidean geometry itself, he says, did not particularly shape the combinatorial work that followed. The habit of being stopped by a clean argument did.

Asked what is in his mind when he designs an algorithm, Karp is almost mechanical. An algorithm is usually the repetition of an inner loop. He visualizes the distance to the desired solution shrinking until it hits exactly. Each step has to get closer, and you need the certainty of convergence. On the traveling salesman problem he could watch a particular function being minimized, successive approaches to the optimum, which he found fascinating. Fridman splits the work in two: intuition about what the solution looks like, and the messy proof that it converges at a given complexity. Karp locates the magic in the first kind of watching: the gap decreases monotonically, the metrics improve, and then you hit the optimum.

Don Knuth has described people who take great aesthetic pleasure from contemplating the structure of computational processes and called them geeks. Karp remembers the moment he realized he was one: someone showed him the Hungarian algorithm for the assignment problem. You have n boys and n girls, a matrix of pairing costs, and you want a one-to-one matching of minimum total cost. Forbidden pairs can be treated as infinite. The key observation is a single sentence. Subtract a constant from any row or any column and the identity of the optimal permutation does not change, because every complete matching drops by the same amount, so the comparisons are untouched.

The algorithm starts from a non-negative matrix and keeps subtracting constants from rows or columns, never going negative, until a full permutation of zeros appears. That permutation is cheapest. In practice you slightly oversimplified if you only subtract: you subtract from some rows and columns and add the same constant back to others so existing zeros stay zero, while the total cost still falls. The rows and columns to touch are found by a kind of shortest path through the matrix. Polynomial time, and orderly. If he had mechanical ability, Karp says, he would probably like woodworking — shaping something into something beautiful. The systematic nature of an iterative algorithm gives him the same pleasure. He used to amuse himself by multiplying four-digit numbers in his head and putting himself to sleep by doubling from one until memory failed. A summer job as the barker at a skee-ball game outside Boston — "come one, come all, five cents to play" — put him next to colleagues with no academic bent. Mental arithmetic impressed them.

Fridman notes that Numberphile is one of the internet's most watched science channels, even when viewers cannot follow the details. Karp's explanation is practical. You can test whether a large number is prime. You can solve little missionary-and-cannibal puzzles. It is achievement; it is puzzle-solving. At a higher level you can prove, in an ironclad way, that the angles of a triangle sum to 180. That is an escape from the messiness of the real world, where nothing can be proved. Another attribute of geeks, he adds, is that they are not necessarily endowed with emotional intelligence, so they can live in abstractions without mastering the complexities of dealing with people.

In 1955, as a Harvard PhD student, Karp joined Howard Aiken's computation laboratory, home of the Mark I and Mark IV. The Mark IV filled a room much larger than the office they are sitting in. You could walk around inside it, past rows of relays. The machine would sometimes fail because of bugs, which literally meant flying creatures landing on the switches. He never used that machine for any practical purpose. The lab later acquired a UNIVAC with 2,000 words of storage. Memory allocation was an art: access time from one word to another depended on the word numbers, so you arranged storage to make fetches fast.

Fridman asks whether he was attracted to mathematics made physical. Not at all. He was attracted to the underlying algorithms. Could he have imagined, sixty years on, billions of computers? He could not imagine that, but the laboratory had a sense that this was the wave of the future. His mother told him data processing was going to be really big and he should get into it. "She was a smart woman." He felt it would change the world. He had no anticipation of personal computing, or of walking around with computers in pockets. AI was not on his radar, though he did read Turing's paper on computing machinery and intelligence. He did not think the Turing test was a good test. It was too subjective, and not the right way to calibrate how intelligent an algorithm could be.

The deeper question, Karp says, is whether human-level intelligence is achievable at all. Most of what is called AI operates inside a limited set of ground rules on a precise task. Humans function in changing environments, with emotions, bodies that explore, intuition, and desire. He does not see anything in current achievements that comes close. He does not think there is any computer program that surpasses a six-month-old child in comprehension of the world. Asked whether a Turing machine could in principle match us, he is doubtful. The argument in favor is the brain itself: if you buy the premise that it is an enormous interconnected set of switches, then in principle you could characterize the switches, map the wiring, and simulate it. That may be an existence proof. It is not, he thinks, a feasible way to go about the problem. Acquiring that information would be almost impossible.

Consciousness — subjective experience, knowing oneself — is the example of a mystery we have no clue about. If you try to define "knowing itself" rigorously, you run into a lot of trouble. He knows people who believe general intelligence can be achieved, and some who feel certain the singularity will come, machines will learn more about themselves, and humans will be reduced to an inferior breed. He is doubtful that this will ever be achieved. None of the work in speech, robotics, natural language, or flexible computer assistants comes anywhere near that level of cognition. Fridman offers Moore's law: we think linearly, and we failed to imagine the jump from Mark I to iPhone. Karp does not think any constant-factor improvement changes the picture. Multiplying switch speed by a thousand or a million will not be useful until we understand the organizational principle behind the network.

A combinatorial algorithm, Karp says, deals with discrete objects that occupy states or take values from a discrete set, and that need to be arranged or selected to minimize a cost or to prove that some configuration exists. A graph is the basic example: a set of points, certain pairs joined by edges. In applications those edges are interconnections — switches in a circuit, communication in a community, roads between cities. They can be directed or undirected, with or without weights. School scheduling puts classes on vertices and constraints on edges. The assignment problem is a complete bipartite graph with costs. Logical design asks how many gates you need so that a circuit outputs yes if at least k inputs are ones.

Fridman's favorite is network flow: pipes, water, traffic, communication, supply chains. Edges are channels with capacity; the commodity might be gas, water, information, or products moving from one operation to the next. The central question is the maximum rate from a source to a destination. Karp and Jack Edmonds were, he thinks, the first to give a formal proof that this maximum-flow problem can be solved in polynomial time. Fridman remembers being surprised, even in graduate school, that max flow had a nice fast algorithm. The Edmonds–Karp algorithm is the one named for that work. Before they linger on running times, Karp wants to define what polynomial time actually means.

You have input data — vertices, edges, capacities — and a program built from addition, subtraction, multiplication, division, comparison. A step is one of those operations. An algorithm runs in polynomial time if the number of steps, as a function of input size, grows only as some fixed power: linear, quadratic, and so on. Theoreticians take that to be the definition of efficient, and Karp admits the definition is arguable. An n-to-the-ten-thousandth algorithm is not efficient in any ordinary sense. In practice the jump that matters is often from n squared to n log n or linear, because networks can have millions of elements and anything above n log n is already too slow. The class of problems solvable that way, in the worst case, is P. Worst case is the whole theory: an algorithm that is fast on most inputs and disastrous on one still has a bad complexity. That matters, he flags, because some of the most useful algorithms in practice have a poor worst-case standing.

NP is the class of problems that may be hard to solve, but where a proposed solution can be checked in polynomial time. Clique is the illustration. Finding a complete subgraph of size k is hard. Handed a set of vertices, you can check every pair for an edge, and that is polynomial. Finding is hard; verifying is easy. Every problem in P is also in NP: if you can solve it, you can verify. The converse is the central question of theoretical computer science. School scheduling makes the gap intuitive. Handed a timetable, you can check the constraints quickly. That does not mean you can find one quickly. Checking appears easier, so NP appears much larger than P. Karp keeps inserting the word *appears*. We do not know.

If Fridman made him bet all his money, Karp would bet that P is not equal to NP. The reason is blunt: some of these easy-to-check problems have been around for centuries, studied intensely in mathematics and even more so in the fifty years since P versus NP was stated, and no polynomial algorithm has been found. Factoring goes back to Gauss. Ninety-one is 7 times 13. A twenty- or thirty-digit number leaves you at a loss. Once someone hands you the factors, multiplying them back is instant. If P were equal to NP, every problem whose solution can be rapidly checked could actually be solved in polynomial time. He does not really believe that. Following Stephen Cook, he was instrumental in showing that a huge number of problems inside NP are equivalent: either all of them lie in P, or none of them do. If P is unequal to NP, virtually all the standard combinatorial problems cannot be solved in polynomial time.

Cook's 1971 result is the first and most important stage. The satisfiability problem of propositional logic is as hard as any problem in NP. You have formulas built from AND, OR, and NOT over variables that are true or false, and you ask whether some assignment makes the whole formula true. Karp's four-clause example — (A or B), (A or not B), (not A or B), (not A or not B) — has no satisfying assignment. Cook showed that every problem in NP can be re-expressed as an instance of SAT. The tool is the Turing machine: a tape, a head, a finite list of instructions of the form "if you see this symbol in this state, write, move, change state." Any algorithm on a real computer translates into one on that machine. Any nondeterministic polynomial-time algorithm is a list of such moves, and that list can be written as a logical formula.

When you look at Cook's proof, Karp says, it is not too difficult to see why it works. The implications are staggering. All the problems where solutions are easy to check can be rewritten as SAT. P versus NP becomes the question of whether SAT has a polynomial-time algorithm. Karp encountered the paper at a 1971 conference. SAT, he realized, was a universal combinatorial problem. Experience told him that many other problems seemed to have that same universal structure, so he started looking for reductions *from* SAT. Integer programming was an early one: linear inequalities, but the variables must be integers, in fact 0 or 1, which makes the problem much harder. Restating SAT that way is not difficult. Each variable becomes a 0/1 variable; each clause becomes an inequality.

Clique, or its cousin independent set, shows how the translation actually works. Write SAT as a conjunction of clauses, each a disjunction of literals. To satisfy the formula you pick one true term from each clause, never picking both a variable and its negation. Build a graph whose vertices are those term occurrences. Put an edge between two vertices if they sit in the same clause (you only pick one per clause) or if they are opposite values of the same variable (you cannot make a variable both true and false). An independent set of size equal to the number of clauses is then a satisfying assignment. Fridman still finds it hard to believe that a graph and a logic formula can be friends in this way. Karp does too, in a sense. They have the same expressive power: you can take any one and translate it into the language of the other. Same expressive power is not the same computational complexity. Translation can blow up. What you can say is that either all of these problems or none of them are solvable in polynomial time.

The 1971 paper took 21 fundamental problems of packing, covering, matching, and so on, all in NP, and showed that SAT can be re-expressed as any of them. It was throwing down the gauntlet: there are probably many more. NP-complete versus NP-hard is, Karp says, a small technicality. Decision problems answer yes or no — is there a clique of size 15? Optimization problems return a number — what is the largest clique? The hardest yes/no problems in NP are NP-complete; their optimization counterparts are NP-hard. The equivalence chain is the same. If someone shows P equals NP, or that it does not, what will the proof look like? It will involve concepts we do not now have. If the result is P unequal to NP, the great majority of combinatorial problems, being NP-complete, will not have efficient algorithms for every instance. There is a little hope: not in P only means not efficient on *all* instances. Attention would turn to heuristics and approximations, with a little more acceptance. If P equals NP, the impact is of another magnitude: everything easy to check becomes easy to solve.

Asked for the most beautiful combinatorial algorithm he has come across, Karp chooses stable matching, also called the stable marriage problem. You want to marry off n boys and n girls. Each boy ranks the girls; each girl ranks the boys. A one-to-one matching is stable if there are no two couples where the boy prefers the other girl to his mate and she prefers him to hers — no pair who want to run away, leaving their partners behind. The same idea, not quite in that form, is how medical residents get matched to hospitals. For any set of preferences a stable matching exists, and it can be computed by a simple algorithm due to David Gale and Lloyd Shapley, not to Karp.

Each boy proposes down his list. A girl accepts tentatively and can drop the current partner if a better proposal arrives. Boys never go back: once denied, they do not try that girl again. Girls only improve; boys only go down their lists. The process ends with everyone matched and no pair that wants to abscond. Who is better off? The proposers. Each boy does at least as well as he would in any other stable matching. There is, Karp says, a lesson for the boys: go out and be proactive. Add a real constraint — a husband and wife who want the same city — and the problem becomes NP-hard. Gale died before he could share the Nobel. Shapley later shared an economics prize with someone else for ideas stemming from this matching.

Among his own algorithms, Karp is fondest of Rabin–Karp string matching because it illustrates the power of randomization. The problem is old: does a long string contain a given short word? Classical methods are combinatorial, comparing characters and jumping with a failure function. Rabin–Karp does something else. Treat letters as digits and the alphabet size as the base, so every word is a number. Pick a random prime in a range and take the remainder: a fingerprint, a kind of hash. Slide a window of the pattern's length along the text. Updating the fingerprint when the window moves by one position takes a couple of arithmetic operations, not a rescan. Compare fingerprints. A match is probably a real occurrence, because a random prime makes collisions unlikely; if you hit one, check the original. You get cheap updates and a small, after-the-fact-checkable error probability.

A randomized algorithm, at bottom, is the ability to draw a random number, associate one with an object, or sample from a set. A presidential election, in principle, could be decided by a few thousand randomly chosen voters; the most popular candidate in the sample would very likely be the national winner. You cannot do this in life — everyone wants their vote to count, you cannot sample purely, ties happen — but the mathematics, stripped of that mess, is solid. Primality is the other textbook case. Fermat's little theorem says that if n is prime, then for any a between 0 and n minus 1, a to the n minus 1 modulo n comes back a. Fail once and n is not prime. Random a's that all pass make n probably prime. Miller–Rabin has to be more careful because of pseudoprimes, but the idea is that identity.

Karp used the same sampling idea to count how many solutions satisfy at least one formula in a collection. Direct counting double-counts solutions that hit several formulas. Think of a 0/1 matrix: rows are formulas, columns are solutions, a one means this solution satisfies this formula. You want the number of columns with at least one one. Sample rows in proportion to how many ones they contain, then walk up the column and only count a hit if you are on the earliest row that has that one. Each column is counted once; the estimate is statistically robust. The general principle: if a phenomenon occurs almost all the time, a random sample is likely to hit it. Algebraic identity testing is the same move. Two formulas look different; plug in a random value. If they are not identical they disagree a lot, so a random point exhibits the disagreement.

Everything so far has been worst-case analysis: the algorithm must finish in this many steps no matter the input. Karp's verdict is clean. If worst-case analysis shows an algorithm is always good, that is fine. If it shows the solution is not always good, you have to step back and ask how often you still get a good one. Fridman says we tend to throw algorithms in the trash the moment the worst case looks bad. Karp says that is unfortunate. SAT is NP-complete, so in theory it should not have efficient algorithms. In practice, SAT solvers fairly reliably handle instances with many millions of variables from digital design and program correctness. People in those fields tend to think of satisfiability as an easy problem. They do not need to know its theoretical status. The instances they actually write down are, for reasons not entirely understood, not the hard ones.

Traveling salesman is NP-hard. Using integer-programming codes plus mathematical tricks, people solve geometric instances — cities as points in the plane — to proven optimality with tens of thousands of cities. That size takes a few computer-months. A thousand or two cities is rapid, and the optimality is a proof, not a heuristic guess. There is no polynomial algorithm we believe in, and yet the codes fly. Is there a systematic way to say "in practice this is pretty good"? Average-case analysis needs a probability space, a notion of typical instance, and that is very hard. After the NP-completeness work Karp looked for a way to shed some positive light. He took the easy way out: simplistic assumptions. Generate a random graph by adding random edges until you have enough. In that model he and others proved lovely things. A Hamiltonian cycle — a cycle through each vertex once — is very likely once the number of edges is a little more than n log n, and there is a heuristic that finds it with high probability.

The community got a lot of results. It was a great playground. The field was lukewarm, because the assumptions were so simplistic. After a while he concluded it did not have a lot of bite for practical application. Toy problems. Fridman asks whether you can do what machine learning does at its best: a real data set, a public leaderboard. Not really. Knuth collected a zoo of graphs from various sources, which lets you watch algorithms on different types, but defining the class of graphs you actually care about is already a non-trivial step. There is nothing analogous to a supervised-learning training set for combinatorial problems on graphs and networks. An empirical branch of theoretical computer science, taking Facebook subgraphs and proving things the theory community would respect, has not been achieved. There is a field called experimental algorithmics: people are given a family of examples, or they generate them at random, and they report performance. There is no convincing evidence that the sample is representative of anything at all.

Among open problems, Karp points to a 1979 paper with Richard Lipton. Take an NP problem of a fixed size — traveling salesman on 52 cities — and ask whether there is a small Boolean circuit tailored to that size: edges in, yes or no out on whether a tour of length L exists. If P equals NP, these problems have polynomial-size circuits. The converse is the interesting question. Could a problem have a small circuit for every size, each circuit possibly unrelated to the others, without having a single uniform polynomial-time algorithm that works for all sizes? They proved that if NP had small circuits, the polynomial hierarchy would collapse to the second level. The first level is P. The second is NP: there exists an X such that a property holds. The third is for all X there exists a Y — the game-theory shape: for every strategy of the first player there is a reply. Higher levels pile on quantifiers. If NP has small circuits, three quantifiers, four, any number, buy you nothing. That is evidence, not proof, and the evidence is strange: it says the thing is too bizarre to happen. P unequal to NP is already bizarre. Either way you have to fight the dragon.

Machine learning, Karp says, lives in a different world. Results tend to be empirical, more akin to SAT solvers: we observe that on formulas arising in practice the solver does well. The successes are real — image processing, robotics, language, game playing — and a side effect is that a reputation in the field makes it not too hard to become a millionaire, because companies believe AI will solve all kinds of problems. The limitations are just as real. Convolutional nets generalize amazingly well off the training set, and we have no theoretical understanding of why. The networks are very hard to understand; very little insight comes out. You can tell whether a photo is in another sample. You cannot characterize the features that distinguish the objects. Fridman notes that a neural net is, in a way, exactly the small circuit they were talking about. In a sense yes, Karp says, then corrects himself: it is an algorithm, a computable function; give it input, get output. What it does not have is an algorithmic-style manipulation of the input whose structure you can read. The edges of objects do not emerge from the circuit. It is clear to the circuit, Fridman says, just not to us — the way the brain is unclear to itself. Karp grants the point, then adds that for vision and audition we do have some principles, and for deeper cognitive tasks we do not.

Bioinformatics still amazes him, especially that we are beginning to edit DNA: take a sequence, find it in the genome, do something to it. That is taking biological systems toward the world of algorithms. It also raises ethical questions. Editing an individual is not the same as editing a germline, which affects all descendants. Even on individuals there is hubris: you assume knocking out a gene is beneficial, and you do not know the side effects. Agriculture and medicine could gain a great deal; the ethical problems will sit on the table. On the algorithmic side you can analyze genomic data: which genes operate in a cell and under what conditions, which proteins affect one another, which physically interact, how to sequence and modify them. That is a statistical big-data problem, which makes it computer science. The data sets are growing, along with ancestry, disease tendency, and treatment personalized to a genome — including, for a woman, whether a proclivity for breast cancer is strong enough to act on.

Karp dedicated his 1985 Turing Award lecture to the memory of his father. The fondest memory is watching him at the blackboard, drawing perfect circles by hand, holding the interest of a motley collection of eighth-grade students. On rare occasions Karp could sneak into the classroom. His father was at his best there: he came to life, taught, chatted, ingratiated himself with the students. What Karp inherited was a great desire to be a teacher. He had recently retired, and former students came — people he had done research with, people who had read his papers, people who had sat in his classes. They did not talk about the 1979 paper or the 1992 paper. They talked about what they took away from the classroom: not the details, the approach, the manner of teaching.

In his early years at Berkeley he was exemplary about preparing lectures, always prepared to the teeth, and therefore able to deviate according to what happened in class. Advice for other teachers: the top three are preparation, preparation, and preparation. Preparation gives you the ease to deal with whatever comes up. If one explanation is not getting through, you can do it another way. If students have questions, you can handle them. You can feel the room — the eyes, the questions — and because you prepared, you can dance. Aha moments that make students fall in love with computer science are different for everybody. Some are already running and just need an ear. Some need a prod. Some need to be persuaded to collaborate instead of working alone. Each student has ups and downs. You have to deal with each as a human being and bring out the best. Humans are complicated.

If he could relive a moment outside of family, he would pick the stretch when a lazy undergraduate, still lazy in his first graduate year, started doing research. A couple of summer jobs let him contribute and have an idea. Then a course on mathematical methods in operations research: he gobbled up the material and scored 20 points higher than anyone else, which brought him to the attention of the faculty. It made him realize he had some ability, that he was going somewhere. Fridman closes with Isaac Asimov: "I do not fear computers. I fear lack of them." Karp's own stance, across two hours, is quieter than that. He does not fear computers, and he does not think they are about to surpass us. He is more interested in the gap between observing that something works and actually understanding why.