The Berkeley Science Review: Articles

Faculty Profile
Richard Karp (view PDF)
by Dan Gillick

Forty years ago, Richard Karp joined the faculty at UC Berkeley, and during his tenure helped lay the groundwork for the study of theoretical computer science that underlies much of modern technology, from microchip layout to internet security. He has been honored with such awards as the US National Medal of Science, the Turing Award, and the Fulkerson Prize, among others. In November, he will be awarded the Kyoto Prize, Japan's equivalent of the Nobel Prize (there is no Nobel Prize category for computer science). I spoke with Professor Karp in his office at the International Computer Science Institute, where he continues to work on algorithm design and computational biology.

With the exception of four years at the University of Washington, you've been at Berkeley since 1968. You must like it here.

Oh yes, I'd rather be here than anywhere else.

What was Berkeley like when you first arrived?

Well, in terms of revolutionary activity, Berkeley was a big hub in the sixties. Soon after I arrived, there were major protests against the Cambodian invasion, and then with the People's Park incident—Reagan brought out the National Guard to "protect" the park from people camping out there—it was all fairly exciting. I remember teaching some classes in my house because students didn't want to hold class on campus and at one point bailing out a colleague who had been arrested for participating in a protest march.

You played a role in founding the computer science department?

The first computer science departments were formed in the mid-sixties. When I arrived at Berkeley, there was a kind of unstable arrangement where the electrical engineering department was home to a number of computer scientists, but a group of those had split off to form a new department to serve the College of Letters and Sciences.

As the rivalry that began to emerge between these two departments wasn't healthy academically or socially, the administration decided to create a single computer science division, folded into electrical engineering but with a substantial degree of autonomy. I was not very experienced in academic affairs, having just moved to academia a few years before, but since I had not taken sides in the controversy, I was a logical candidate to lead this new unit. I wasn't a born administrator, so I took the position for only two years, but I played some role in quieting things down, in getting people to accept the arrangement and start building something together.

You're best known for your work on the computational complexity of algorithms. What is an algorithm?

An algorithm is a systematic procedure for performing a computational task. In school we learned algorithms for doing arithmetic—for addition, multiplication, long division. Some of us may have learned the Euclidean algorithm for finding the largest common factor of two numbers. Algorithms are everywhere. At the core of every information processing application, there's an algorithm. Whether it's processing search queries or routing messages through a network or conducting auctions over the web, algorithms are at the heart of it. At the core of all the cryptographic protocols that underlie e-commerce, there's an algorithm for encrypting data which depends in turn on an algorithm for testing whether a number is prime. That algorithm can be written down in a few lines, but it's very subtle and without it we wouldn't be able to conduct business over the internet the way we do.

What about computational complexity?

The first requirement of an algorithm is that it should be correct. It should do what it's supposed to do. Beyond that, it should be efficient. The primary way we measure efficiency or cost—the technical word is "complexity"—of an algorithm is by the time it takes to execute — roughly speaking, the number of basic steps. I've spent a lot of my time devising algorithms that are efficient by that measure.

So computational complexity is about how many steps an algorithm takes from start to finish?

You'd like to have efficient algorithms for practical reasons, but computational complexity is a theoretical field concerned with fundamental laws or limits that say you simply cannot avoid spending a certain amount of time solving some type of problem. Most people are familiar with some basic laws of physics—you can't build a perpetual motion machine, nothing can travel faster than the speed of light, well, there are laws of computation also. In particular, I've been interested in combinatorial search problems, where you are looking for arrangements of finite sets of objects that satisfy some constraints or conditions.

How did you first encounter these kinds of problems?

My father was a school principal and every fall before classes started he tried to solve a complex scheduling problem. He was looking for an arrangement that satisfied a variety of constraints: certain teachers were only available at certain times, certain classes required particular classrooms, certain pairs of classes shouldn't be held at the same time. He got out a bunch of index cards, laid them out on the kitchen table, and starting shuffl ing them around. I tried to help and that was my first exposure to this type of problem.

So how hard is the scheduling problem?

In general, combinatorial problems like this one, which arise in commerce, in physical sciences, in engineering, even in the humanities and social sciences, can be compared to searching for a needle in a haystack. There are a vast number of ways the objects can be arranged—assigning classes to timeslots, for example—but only a few meet all the requirements. So the question is, are there shortcuts? Some problems have clever, efficient algorithms, but for most of the problems that come up, there seems to be no radical shortcut. You can solve small examples, but as the size grows—the number of classes to schedule gets bigger—the running time of even the best algorithm tends to explode. That is, it roughly doubles every time you increase the size just a little bit.

How is this related to your famous 1972 paper?

Basically, people began to ask whether for these problems, exponential growth was inherently necessary, whether there was a law of computation that said you couldn't avoid such an explosion in running time. We still don't know the answer to that. What I was able to do, following the lead of a former Berkeley professor named Stephen Cook, was to show that 21 different problems, having no overt similarity in their descriptions, are actually equivalent in the sense that if you could solve any one of them efficiently, you could solve all of them efficiently.

So even though nobody has proved that no efficient algorithm exists for these problems, you started mounting evidence that strongly suggests this is true. That's right. I used a technique called "reduction" to show that a new problem is as hard as any in the set. You imagine you have an efficient algorithm for solving the new problem and show that you could use the solution to solve some other problem already in the set. By now we have thousands of such problems, with more being discovered every day.

Now you've changed focus—you work in the intersection of computer science and biology?

Yes, I've been working on computational molecular biology since 1992. I work on other things too—problems in networking and other general algorithmic design problems, but a lot of my effort is devoted to problems arising in biology.

This work seems much less theoretical. How did you get into biology?

Well, there were a lot of smart people who were beating me at my own game. The techniques became very sophisticated. I had worked on applications before and I thought I might have an edge because of my knowledge of combinatorial algorithms. Also, biology was increasing in importance, and better yet, it was a subject you could explain to your mother or your cousins. I guess another reason was a sense of competitiveness. Some of my colleagues were going into that area, and I thought if they could do it, I could do it too.

How did the transition work out?

I guess I thought I would come riding in on my white horse with my combinatorial skills and that everything would be easy, but it hasn't been exactly like that. First of all, it's not clear what is meant by a correct algorithm since typically you don't really know the right answers. The biologist is looking for some explanation for a phenomenon and wants to understand how a particular cellular process is regulated, for example. It's not the case that you can recognize the right solution when it's handed to you. It's not like these well-defined theoretical problems where you can verify a solution by inspection. When you come up with a neat algorithm, it's really more a matter of the confidence that biologists have in the results that determine whether it will be accepted by the community rather than some theoretical criterion. And you have to develop good software with good interfaces, and you have to make contacts to get people to use it. So there are a lot of things involved besides the core algorithm itself. I've found you have to really be part of the team and have close connections with biologists. I tend to like to sit alone in my cubby hole, playing with some well-defined problem. Fortunately, I've had postdocs and visitors and other collaborators who help with the liaison with biologists, so I get good feedback.

Dan Gillick is a graduate student in computer science

Want to know more? Check out:
Inamori Foundation (Kyoto Prize):
inamori-f.or.jp/e_kp_lau_thi.html

Comments on this article? Drop us a line at with 'letter to the editor' in the subject!