change the problem or somehow get
around the complication in tractabil-ity. 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 algo-
rithms 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
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
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
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
problem in software
is assuring that
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.
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
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
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.