i guess what
i provided was a
definition and result—
result crystallized it.
I was reading their papers, but not
having personal interaction with them.
at some point you picked a thesis advi-
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
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
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 inci-
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 profes-
sor at Berkeley, not as a lecturer, is that
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 sIGac T. 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
How long had sIGac T been around in
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
No. I was denied tenure by the math-
on discrete algorithms,
contact: david s. Johnson,
acM International workshop
on Timing Issues in the
and synthesis of digital
contact: charlie chung Ping chen,
The 39th annual acM
sIGPLan-sIGac T symposium
of Programming Languages,
contact: John field,
acM International Health
contact: Jiming Liu,
January 30–february 3
contact: Michael da Raadt,
on agents and artificial
Vilamoura, algarve Portugal,
contact: fred ana,
second acM conference on
data and application security
san antonio, TX,
contact: elisa Bertino,
b Cook’s thesis title was “On the Minimum
Computation Time of Functions.”
c The ACM SIGACT Symposium on the Theory