Richard Karp

When theoretical computer scientist Richard Karp began his graduate studies at Harvard University in 1955, there were no computer science departments. No one had even coined the term “computer science.” The discipline was “somewhere between nonexistent and primitive,” he recalls.

Nearly 60 years later, Karp, who at 78 still maintains an active research career, has done more than almost any other theoretical computer scientist to shape the discipline. In addition to writing a 1972 paper, “Reducibility Among Combinatorial Problems,” that is widely viewed as one of the most influential papers in theoretical computer science, he has made seminal contributions to nearly every area of the subject. “It would take hours to give even a hint of his many great ideas,” says Avi Wigderson, of the Institute for Advanced Study in Princeton, N.J. “In everything he has touched, he has produced important papers.”

A legendary teacher who has mentored more than 40 doctoral students, Karp has shaped theoretical computer science not just through his ideas but also by means of his famously approachable persona, says Wigderson, who first met Karp at a conference toward the beginning of his own graduate studies in 1980. “One of the most amazing things that is still true of this community is how easy it is for a first-year graduate student to meet someone like Karp, one of the biggest names in the field,” Wigderson says. “The social structure of our field is very friendly, and he has had a large part in this.”

Karp “keeps his greatness on a very short leash,” says Christos Papadimitriou, a colleague of Karp’s at the University of California, Berkeley. “There’s modesty and humility in his manner, but when he opens his mouth, people stop and listen.”

•••

Karp’s affinity for mathematical subjects manifested itself early. As a child, he enjoyed analyzing baseball as a random process or wowing his friends by multiplying four-digit numbers in his head, and in tenth grade he used to fake illness so he could stay home and solve geometry problems. When he became a math major at Harvard, however, Karp discovered that purely axiomatic mathematics left him unmoved, on the whole. Instead, he discovered an affinity for probability, discrete mathematics and algorithms — subjects grounded in real-world problems. That preference has never left him.

“I like to have the sense that I’m doing something that’s meaningful in the world,” Karp says. “That always guides me in choosing what to work on.”

When Karp finished college, his mother offered him a prescient piece of advice, Karp says: “Young man, go into data processing.” As Karp pursued his graduate studies at Harvard’s Computation Laboratory, “there really wasn’t much [computer science research] to dig one’s teeth into,” he recalls. Nevertheless, he says, “there was a feeling that great things were in the air. It was a very propitious time to start a career.”

There was no such thing as an academic career in computer science back then, but Karp landed a “dream job” at IBM’s Thomas J. Watson Research Center, where he worked from 1959 to 1968, first at the Lamb estate in Croton-on-Hudson, N.Y., and then in Yorktown Heights, N.Y. Ninety percent of the time, he recalls, he was free to concentrate on his own research, with stellar colleagues and few responsibilities. During this time, in collaboration with researchers such as Ray Miller and Michael Held, Karp carried out foundational work on models of parallel computation and developed algorithmic approaches to several combinatorial problems, including the famous Traveling Salesman problem.

In 1967, Karp paid a visit to Jack Edmonds, a mathematician and computer scientist at the National Bureau of Standards. Edmonds emphasized the importance of the concept of “polynomial time,” the idea that an algorithm is feasible only if the number of computational steps is bounded by the size of the input raised to some power (in contrast with “exponential time,” in which the number of steps explodes exponentially). Edmonds showed Karp several remarkable algorithms for combinatorial problems and told him that he believed the Traveling Salesman problem could not be solved in polynomial time. “Jack just blew me away,” Karp recalls. It was the “most eye-opening single day I think I’ve ever spent.”

•••

While at IBM, Karp taught courses at various universities in New York City and discovered that he had a gift for teaching. In 1969, he decided to move into academia, joining the faculty at Berkeley, where he became the chairman of the newly formed computer science division in 1973. “Being a professor at a great research university is the best job I can think of,” he says.

Karp, who was awarded the UC Berkeley Distinguished Teaching Award in 1986, is an exceptionally clear teacher, says Wigderson, who was a postdoc at Berkeley in the early 1980s. “I went to every class he taught,” he says. Karp himself, somewhat ruefully, attributes the clarity of his teaching to “preparation, preparation, preparation.” He took the attitude, he says, “that every lecture class was like a performance of ‘King Lear.’”

In 1971, Karp read a seminal paper by Stephen Cook, of the University of Toronto, which studied the difference between two classes of problems: P, the class of problems that can be solved in polynomial time, and NP, the class of problems whose solution, if provided, can be verified in polynomial time. Cook asked whether the classes P and NP coincide, a question that is still one of the biggest unsolved problems in computer science today. He then showed that a particular logic problem called “satisfiability” is, in a precise sense, as universal and as difficult as any problem in NP can get, which means that if it can be solved in polynomial time, then so can every problem in NP. This property came to be called “NP-completeness.” (Soviet computer scientist Leonid Levin independently developed this concept at around the same time.)

Cook had approached the problem of NP-completeness from the point of view of mathematical logic. Karp’s approach to computer science, by contrast, was firmly grounded in real-world algorithms; he liked to fiddle around with concrete examples, filling page after page with computations. In his work on the Traveling Salesman problem and other optimization questions, he had experienced exponential explosions firsthand, and he had an instinctive feeling for which problems were inherently hard.

When Karp saw Cook’s paper, he was instantly convinced that a host of algorithmic problems have the same universality property as satisfiability. In 1972, Karp wrote a follow-up to Cook’s paper in which he demonstrated 21 problems that, like satisfiability, are NP-complete — not abstruse, cherry-picked theoretical problems, but bread-and-butter computational problems that are central to many different applications.

Karp’s paper “started an avalanche,” Wigderson says, as researchers began to realize that in fact, thousands of problems in all areas of science — economics, biology, engineering and pure mathematics, to name just a few — are NP-complete. “It connected so many fields of science under one umbrella.”

In the present era, a new paper with “NP-complete” in its title appears roughly once an hour, Papadimitriou says. “It’s mind-boggling, the impact of this concept.”

Karp’s paper on the subject is “clearly one of the most important science papers ever written,” Wigderson says.

•••

Karp’s work on NP-completeness alone would have secured his reputation for posterity. But instead of resting on his laurels, Karp proceeded to make fundamental contributions to a wide range of problems in theoretical computer science. In the early 1970s, for instance, in collaboration with Edmonds and John Hopcroft, Karp developed efficient algorithms for two problems concerning networks: the bipartite graph matching problem, about how to match up pairs of nodes in a network, and the network flow problem, about finding the best routes to flow materials through a network. During the 1980s, to address the question of why many NP-complete problems seem easy to solve on inputs derived from the real world, Karp developed the field of probabilistic analysis of algorithms, which seeks to understand how well an algorithm can be expected to perform on average, instead of in the worst-case scenario. He has also made foundational contributions to the study of algorithms that incorporate randomness, and to the problem of locating data in peer-to-peer networks.

Karp “has made amazing contributions to everything that is important in theoretical computer science,” Papadimitriou says. It’s rare for a computer scientist to start over, as a beginner in a new field, as many times as Karp has done, according to Papadimitriou. Doing so “takes intellectual courage, flexibility and humility,” he says.

In the early 1990s, Karp made one of the biggest leaps in his career, into the nascent field of computational biology. At the time, he recalls, there was a general feeling that biology was going to be the most important science for the coming generation. Many of the problems in modern biology are combinatorial in nature — understanding the language of the genome, for example, or studying networks of interacting proteins — and are exactly the sorts of problems that fit Karp’s natural taste and expertise. In 1994, at an age when many scientists start to think about retiring, Karp moved to the University of Washington, where he spent four years “sitting at the feet of biologists and trying to learn the trade” before returning to Berkeley in 1999.

Today, computational biology has attracted some of computer science’s best talents, Papadimitriou says, due in large part to Karp’s “brave move” in entering the field in its infancy. “He pointed the way.”

At 78, Karp is again reinventing himself, this time as director of the newly founded Simons Institute for the Theory of Computing on the Berkeley campus, whose mission — to promote theoretical computer science as a lens on the sciences — fits perfectly with Karp’s own philosophy.

Administrative positions aren’t Karp’s cup of tea, but his dedication to the profession made the decision to lead the new institute a clear one. “I thought it was appropriate for me to take this on, rather than one of the younger people whose careers are peaking right now,” he says. “My focus will be not as much as before on my own individual research, but rather in creating an environment that will foster the ambitions and the activities of younger scientists.”

Still, Karp plans to make time for his own research. “I hope to sneak away and do a little bit of doodling on the blackboard,” he says.