The Charles Babbage Institute holds one of the world’s largest collections of research-grade oral history interviews relating to the history of computers, software, and networking. Most of the 400 interviews have been conducted in the context of specific research projects, which facilitate the interviewer’s extensive preparation and often suggest specific lines of questions. Transcripts from these oral histories are a key source in understanding the history of computing, since traditional historical sources are frequently incomplete.
The following is a condensed version of an interview with A.M. Turing Award recipient and ACM Fellow Stephen A. Cook, considered one of the forefathers of computational complexity theory. The original interview was conducted by CBI researcher Philip L. Frana in Toronto, Canada, in 2002 following Cook’s lecture at the University of Minnesota as part of the Cray Distinguished Speaker Series. After describing his background, including his influential 1971 presentation on "The Complexity of Theorem Proving Procedures," Cook discusses his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his 1982 A.M. Turing Award for "contributions to the theory of computational complexity, including the concept of nondeterministic, polynomial-time completeness. The ensuing exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science."
Cook further discusses the feasibility of solving the P versus NP problem, which has recently received renewed attention given increasingly powerful computational capabilities and the decreasing cost of computing. In a September 2009 Communications article, Lance Fortnow wrote that Cook’s work on computational complexity theory has motivated a great amount of research into decision problems with "feasible" decision procedures in the areas of workplace efficiency, transportation, logistics, and manufacturing. It also laid the groundwork for discoveries of NP-intermediate integer factorization algorithms like the high-profile Shor’s algorithm for breaking public-key cryptography.
The complete transcript of the original interview is available at http://conservancy.umn.edu/handle/107226.
Were your parents mathematicians?
My father was a chemist. He got his Ph.D. at the University of Michigan and worked for many years at a subsidiary of Union Carbide. Later he became adjunct professor at the University of Buffalo. My mother eventually had two master’s degrees, one in English and one in history. She was mostly a house-wife but did some teaching at Erie Community College. She taught English for a number of years.
How did you make the decision to attend Michigan in 1957?
My parents were alumni and they met there. Some other relatives also attended Michigan. My mother grew up in Michigan.
I take it you knew that the mathematics and computer science programs were strong at Michigan at that point?
Not especially. I knew that Michigan was generally good academically. I was not thinking of computer science when I went to Michigan. Computers were pretty new then. This was 1957.
What were you thinking about doing when you went to Michigan?
Engineering, actually. I enrolled in the College of Engineering in Engineering Science, and I had quite an interest in electronics. Clarence, NY, is where we were living at the time, and Clarence had, and still has, a prominent citizen named Wilson Greatbatch. Greatbatch was inducted into the National Inventors Hall of Fame for inventing the first implantable artificial cardiac pacemaker. [Greatbatch, who held more than 325 patents and was a recipient of the LemelsonMIT Prize, passed away September 27, 2011. Ed.] He was developing the electronics for it while I was in high school so I learned and worked with him, just helping him solder up circuits. This was the early days of transistors, so I got quite interested in electronics.
He recommended Michigan?
No, it was just my parent’s alma mater. My older brother had also gone to Michigan.
I think there was a feeling that there were certain problems that just seemed to be hard.
I don’t know too many people who were at Michigan at that time. Did you study with Bernie Galler?
Yes, absolutely. I took a course from him my very first year. It was a one-hour credit course in programming—that was my introduction to programming.
He said you did very well. I took the liberty of asking him about you. He remembers you. were you learning SNOBOL?
Not SNOBOL, but it was a Michigan product. I remember the Graham-Arden compiler. I can’t remember the programming language. There was a homegrown algebraic programming language.
Was it MAD, the Michigan Algorithmic Decoder?
That sounds right. That might have been it.
Do you remember any of your other mentors from those days?
At Michigan, the math guy was Nicholas Kazarinoff. I was in engineering science and I took a calculus course where I performed well and he noticed me. That was really my best subject all along. He encouraged me to jump into a third-year course the second term and so I took an accelerated mathematics program. Eventually I transferred into the Bachelor of Math and Science degree program after two and a half years, and majored in mathematics.
Was it difficult to make that adjustment?
Yes. It was clear that mathematics was my real area. Of course, I was good in mathematics in high school, but I didn’t know any mathematicians. I didn’t really know what mathematicians did.
Who made the recommendation that you study at Harvard upon graduation?
That was one of the great mathematics departments. I applied at other places too, like Princeton and Berkeley. I don’t remember exactly why I ended up at Harvard.
Was Alan Cobham already at Harvard at this time?
Well, no. Before I got there he was a graduate student in the mathematics department and was close to getting his Ph.D. He wrote a thesis, but he didn’t bother to complete the minor thesis requirement. Instead, he just went off to work for IBM Research in Yorktown Heights.
Did you have a major professor in mind when you went to Harvard?
No, and I didn’t really know what I wanted to do either. I put down algebra as my area. I got more interested in computers when I took a course with my eventual advisor, Hao Wang. He wasn’t in the mathematics department; he was in applied physics.
What was your thesis topic?
We didn’t have a real master’s thesis. The master’s degree was something you picked up, just course work really.
So it was just a stepping-stone?
Yes.
In one of your lectures you talk about Cobham’s question, "Is multiplication harder than addition?" as being inspirational to you. Was that a turning point?
That was one thing. Yes, he wrote this interesting paper on the intrinsic computational difficulty of functions, which I read. That was an influential paper for sure. There were other things around too. Michael Rabin was interested in the same kind of problems and he had written articles, and then there were other papers. I think I mention them in my Turing Award article.a
Right. Were Princeton faculty and students visiting Harvard in those days, or were you going down to Princeton?
No, I never went to Princeton. James Bennett’s thesis was quite influential, but I never met him. In fact I think he dropped out of the academic picture as soon as he got his degree. I did meet Bob Ritchie. I think he came up to visit, I think that was the only Princeton connection I can remember.
But you were reading their papers?
I was reading their papers, but not having personal interaction with them.
I guess what I provided was a definition and result—the NP-completeness result crystallized it.
At some point you picked a thesis advisor.
Yes, I had taken a couple courses from Hao Wang. We got along. He wasn’t especially interested in complexity, but he was a logician and he had an interest in computation and he had done work in automatic theorems before.
You received your Ph.D. in 1966. What was your thesis?
It was on the complexity of multiplication,b so that was right in line with Cobham’s question.
You immediately took a job at UC Berkeley in 1966?
Yes, that’s correct.
Did you finish in the middle of the term?
No. I finished in the spring and spent the summer in Europe, and then went off to Berkeley.
What was it like to be a Midwesterner who moves out to California? Many people have found that a very easy transition, but others have found it very difficult.
There wasn’t a huge difference as far as the atmosphere on the university campus at Berkeley. Of course that was the 1960s so there was a lot more student foment.
You were there at a time of a great deal of student organizing.
There was indeed. The Free Speech movement was in full swing and there was tear gas on campus.
You remember some of these incidents?
Yes. There were times when we couldn’t get to the campus because there were demonstrators in the way.
Did you have a role?
No, I was just an observer. I wasn’t politically very active.
You were hired as an assistant professor at Berkeley, not as a lecturer, is that right?
That’s right. My position was in the mathematics department and I was actually cross-appointed with something in the computer center. Initially, I had no connection with the computer science department, which was just starting out then.
I realize that research and discovery is not always an evolutionary process, but this must have been a time that was most critical to you in preparing for your 1971 presentation on "The complexity of Theorem Proving Procedures" at ACM SIGACT. Was NP-completeness something you’d been thinking about hard at Berkeley?
No. I was thinking about complexity issues, but the specific idea of NP-completeness didn’t come to me until immediately before giving the paper. It was gelling from other ideas I had been thinking about.
How long had SIGACT been around in 1971?
It was pretty new. I’m pretty sure this was the third meeting.
Had you attended other meetings?
Yes. I had papers in every conference of STOC,c as we now call it, for about 15 years.
You taught at Berkeley for four years, from 1966 to 1970.
Yes, that’s right.
And after four years you decided to move on?
No. I was denied tenure by the mathematics department. Tenure decisions weren’t as open then. I don’t know what information was presented to the department. The entire math department took a vote—I know that. But I don’t know what kind of evidence was presented or what the basis for the decision was.
Was that a pattern? Did you have friends that suffered the same problem, in your small circle?
My natural colleagues tended to be in computer science departments and I think that made a big difference. Subsequently, I had no trouble getting offers from computer science departments. My field may have been a little too new to be accepted in mathematics.
This was right around the time that Dijkstra’s tenure was denied in Amsterdam too.
Was that also a mathematics department decision?
Yes. He then went on to Austin, Texas. I wonder if it wasn’t the same problem that he faced.
I guess so, in the sense that the field was not completely respectable, mathematically. I had training and there was a strong group of logicians in Berkeley and I had something to do with them, and I think they had some interest in my work, but apparently not enough.
Toronto hired you as an associate professor in 1970?
Yes, that’s right. I think I was hired as an associate professor and then got tenured a year later. I had other offers too. I had an offer at Yale.
Why did you pick Toronto over Yale?
The city, certainly, is much nicer, and the department was better established. Yale’s computer science program was just starting up and it wasn’t clear how well it was going to go. There were several interesting people here. An excellent departmental chair, Tom Hull, really established things here. He did a lot of early hires and set it up as one of the premier departments in the continent.
Just because the problem is NP-complete does not mean that you should not try to solve it.
When was the department established here?
There was first a graduate department and then an undergraduate department. The undergraduate department started up about 1969 or 1970—about when I came.
You settled not far from home.
Yes. I grew up near Buffalo, and we had gone to Ontario resorts in summers.
Was the department as theoretical an institution as it is today?
I think numerical analysis was a strong feature, as it was in many early departments. There were also a couple of physicists, Kelly Gotlieb and Pat Hume. They are both retired now. Kelly is very active in ACM. He’s in his 90s, but is co-chair of the ACM awards committee. He may have been the first chair of the department.
Who were your early colleagues?
Allan Borodin was probably closest. His office was right across the hall. He was a Cornell graduate, hired the year before me.
Did you know him previously?
No, I knew vaguely of his work. I met him during my first recruiting trip, and we got along fine.
What kinds of things were you teaching when you first arrived?
My first appointment was cross-appointed in mathematics. That lasted for a year or two and then I switched completely to computer science. I did teach some math courses. I taught a course in logic, for example. I also taught first-year programming—I did that at Berkeley too. I taught first-year computer programming a few times. I did teach graduate courses in my own area, in computational complexity.
Were there not the rivalries up here between the mathematicians and computer scientists?
I’m not sure that the mathematicians totally appreciated my work. I think there was a feeling on their part that they should—a feeling that this is an up-and-coming subject and they should have something to do with it. Yet I didn’t have too much to do with the members of the mathematics department, and that’s one reason I decided to switch over entirely to the computer science department.
Within a year you had presented your paper on the complexity of theorem proving procedures at the Symposium on the Theory of Computing. Was there an immediate and positive reaction to your paper? The very next year R.M. Karp shows that 21 problems are NP-complete. Was it something that was on a lot of people’s minds?
I think so. I think there was a feeling that there were certain problems that just seemed to be hard. Rabin was also interested in these. I remember he was quite interested in the traveling salesman problem, and was trying to find ways to get lower bounds on the complexity. So I would say yes, there was something in the air for sure. I guess what I provided was a definition and a result—the NP-completeness result crystallized it.
[The traveling salesman problem is a graph theory problem that asks, "Given a map of N cities connected by roads, can a salesperson visit all the cities exactly once within some given number of miles?" The traveling salesman problem is a so-called infeasible problem in computer science, and is therefore unlikely to be computable in polynomial time; the problem is only solved in exponential time. Some readers may quibble with this definition; fuller explanations are found in: Flood, M.M. "The Travelling Salesman Problem," Operations Research 4 (1956), 6175; Hoffman, A.J. and Wolfe, P. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, E.L. Lawler et al., Eds. (Chichester: John Wiley, 1985), 116; Reinelt, G. "The Traveling Salesman: Computational Solutions for TSP Applications," Lecture Notes in Computer Science 840 (Springer-Verlag, Berlin, 1994).—Ed.]
In your lecture at the University of Minnesota you noted that you need to remind some of your new students that all problems in NP are not hard.
Yes.
I gather that that’s how this mythology sprung up that NP problems are hard?
Some people even think NP stand for "Not P," but it stands for non-deterministic polynomial time. So we have these contrasting classes, P and NP. The simplistic assumption is that the P ones are the easy ones, and the NP are the hard ones. And of course P is the subset of NP. It’s the NP-complete ones, the subset of NP problems, which are the hard ones.
Much of this is covered in the chapters of just about any introductory computer science textbook.
Yes.
The idea of time being the most important complexity measure seems rather straightforward to me now because I’ve heard it and read it several places, but it apparently wasn’t.
I think time was an important measure. It was Alan Cobham who was trying to think of some intrinsic measure like "work," but in fact his theorem was about the characterization of polynomial time, so that was the thing he talked about—time. Time seemed to be the most obvious measure of complexity. Certainly space memory was also considered right from the start.
You and Richard Karp were colleagues at Berkeley?
We overlapped at Berkeley. He came to Berkeley from IBM a year or two before I left, so I knew him.
So he returned home from the SIGACT symposium, and started looking at these problems more carefully.
Yes, that’s right. I think he toured the states talking to people about them, and coming up with new problems.
Is it fair to say, then, that Karp is your ‘popularizer’?
Yes. He did a tremendous thing—there’s no question about it. I certainly didn’t realize there were so many natural computational problems out there that turned out to be NP-complete.
I’ve always been interested in things that had a logical flavor to them, like formal correctness of programs.
Between 1970 and 1980 you received several grants from the National Research Council to work on this problem and others. In 1975, you are promoted to full professor at the University of Toronto.
Yes.
And then followed a number of awards: the E.W.R. steacie Memorial Fellowship to support fundamental research essential to the development of science; the Izaak Walton Killam Memorial Research Fellowship from the Canada Council for the Arts.
Yes.
And in that period too, in 1982, you were awarded the ACM A.M. Turing Award for, among other things, your contributions of complexity theory.
Yes. And of course the trigger was the theory of NP-completeness.
In 1985 you became a university professor. Numerous teaching awards followed.
A couple.
You were awarded the CRM/Fields Prize in 1998. What is the Fields Institute? A mathematics institute?
It’s a mathematics institute, right. It’s on our campus although I guess it’s separate. It’s a bit like the Isaac Newton Center at Cambridge. They have a building for mathematics research. They sponsor programs and they have emphasis programs in different areas in mathematics.
The Mathematical Intelligencer declared the P versus NP problem one of the three greatest math problems of the next century. Where does this perception come from?
It seems to be really relevant to the real world—probably more than the other problems on the list. It’s not clear what impact on the world the other very interesting problems have, though they certainly could impact mathematics. If P equals NP, it could have a dramatic effect on the world. More likely P is not equal to NP. There the impact would still be good. It would lead to the possibility of proving cryptographic protocols are secure, which is something we can’t hope to do at present.
One of your audience members said that NP-completeness is sometimes identified on the basis of—as he called it—an "unrealistic" example. I gathered he was trying to argue that there was a disconnect between the theory and human experience on some level.
I think he was referring to the fact that some problems are NP-complete but still seem to be, in practice, solvable. So that’s a question of what class of inputs you want to use. Every NP-complete problem is easy to solve for some inputs and maybe in some cases the inputs you really are interested in are the easy ones. So, in that case, saying it’s NP-complete is misleading. Even for the original NP-complete problem of satisfiability, the fact that it’s NP-complete hasn’t stopped this big industry of programs that they’re solving the satisfiability problem with—in some cases, very dramatic and useful successes. As I mentioned in the talk, they’ve been able to verify large chunks of a microprocessor by proving unsatisfiable gaps that it causes with the tens of thousands of variables. And so there are certainly some. Just because the problem is NP-complete does not mean that you should not try to solve it.
I’m wondering if this isn’t the same stumbling block, on a very general level, that other disciplines are struggling with. In genomics and bioinformatics they now talk about empirical laws that haven’t found their theory yet. They say, "Don’t worry about proving these things—they’re empirically derived from computations."
In bioinformatics there are lots of computational problems as you say, and I’m sure that many of them are NP-complete or NP-hard in their full generality and that just means you have to change the problem or somehow get around the complication in tractability. Or perhaps the inputs that you’re really interested in may not be hard.
Do you consult with the bioinformatics people in Toronto?
We don’t have a strong bioinformatics group. We do have people in the medical sciences interested in the subject. When we have talks I always attend them and I’m interested in the subject.
Can you talk about randomizing algorithms and Boolean circuit complexity being a key to P not equal to NP.
That’s a possible approach and there’s an intriguing connection between Boolean circuit complexity and the P and NP connection.
How often do you get messages from people who say they have solved the problem?
Not that often. I probably get one a month. They don’t say they have solved the problem necessarily. Rather, they ask about it and sometimes they’ll send a program or an algorithm or they’ll ask if a certain approach works. In one case somebody sent a program for solving the Mine Sweeper problem, which is NP-complete. He didn’t know what to do with it and he didn’t want to tell me the algorithm because he was afraid I would steal it and take the million-dollar award in the Clay Mathematics Institute Millennium Prize competition.
Can the problem be solved?
It’s possible. It’s not quite that way, of course. There are two ways the P vs. NP question can be solved: P equals NP, or P does not equal NP. Most of us think it will be solved by showing P not equal to NP. But if it is solved by showing P equals NP, then it would have dramatic implications for mathematics and it might—I can’t say for sure—but it might lead to solutions to all the other problems.
Why do complexity theorists think that P is not equal to NP?
I think there are two main reasons. One is that computer scientists are really good at finding efficient algorithms to solve computational problems. We’ve been doing this now for 30 or more years, probably 40 years. There have been detailed courses on it, and mathematical successes. And as far as the NP-complete problems go, many of them are really useful in industry. Lots of people, not just academic computer scientists, but real people in the field—programmers and engineers—have been trying to solve these problems efficiently. And of course they’ve all failed to solve any of the NP-complete problems, at least in finding provable poly-time solutions for any of them.
The fundamental problem in software is assuring that it’s correct.
So that’s the one side. The other side is we think, assuming P not equal to NP, why haven’t we proved it? It just seems to be very difficult. It’s much easier to find an algorithm to solve a problem to show it’s in P than it is to prove it’s not in P because you have to rule out every possible algorithm. We know that’s difficult and there is this sequence of inclusions of complexity classes; log-space is a subset of P, which is a subset of NP, which is a subset of P-space. And we know the first one: log-space is a proper subclass of the last one, P-space, by a simple diagonal argument, and therefore one of the adjacent conclusions has to be proper but we can’t prove any of them are proper, so that’s just good evidence we’re not good at establishing separations that are there.
Do you expect a winner anytime soon?
Yes it could happen. I’m guessing it’s a feasible problem to solve. Maybe we have to develop more techniques to solve it, but it’s going to be solved eventually.
One of the other areas that you’ve been working on is assertions. I interviewed Tony Hoare in 2002; How did you come into contact with axiomatic semantics and assertions? Is that a relatively recent area of interest to you?
I did that work in the 1980s. I’ve always been interested in things that had a logical flavor to them, like formal correctness of programs. People in this department were interested in formal correctness and so I was aware of Hoare’s work. Hoare developed these rules for proving the so-called "Hoare triples." For each instruction he would have a triple that defined the instruction in some sense. But he didn’t prove anything about the whole system that he got. So I was just trying to think in some sense, ‘These rules must be complete.’ I was trying to figure out the sense in which they were complete.
Microsoft hired him to help introduce assertions into their operating systems.
The fundamental problem in software is assuring that it’s correct. There are some fundamental problems writing it, but once you’ve written it you have to somehow debug it and try to develop your confidence that it’s correct. From early on, various people have said we need a way of mathematically certifying the software. Coming up with formal assertions of specifications and formal proofs that it meets the specifications with ‘assertions’ seems a very natural way to do that.
Hoare said to me that, just before he left Oxford, teaching was moving away from knowledge-acquisition through induction to more collaborative group activities and a dialogue-oriented approach. Does that sound familiar to you? Has the teaching here changed over time?
I haven’t really changed my method of teaching courses, which is the traditional one of lectures, consulting, office hours, and answering email questions. That’s the way most of us still work here. The previous dean had every department develop a seminar course for first-year students so there’d be more close contact with regular faculty members. I guess that’s one pressure. I don’t know if it’s radically different. These seminars were to be small and perhaps a little more informal. We have tutorial sessions led by graduate students in all our courses. The idea is that classes are supposed to be smaller and more interactive.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment