ematics 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 prob-
lem, 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 di-
jkstra’s tenure was denied in amster-
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 pro-
fessor 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 problem is
NP-complete does not
mean that you should
not try to solve it.
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
when was the department established
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
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 teach-
ing 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 com-
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
[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),
61–75; 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), 1–16; Reinelt, G.
“The Traveling Salesman: Computational Solutions for TSP Applications,”
Lecture Notes in Computer Science 840
(Springer-Verlag, Berlin, 1994). —Ed.]