before the walls of the garbage-crunching machine started closing in,
we’ve got a really bad feeling about them. They look as if they are intracta-
ble, and this would be bad news, as it would mean that we would be con-
fronted with problems of considerable practical significance that simply
can’t be solved in a reasonable period of time.
Schedule construction and the traveling salesman problem are only a
few of more than a thousand such problems that are currently in limbo
with regard to whether they are intractable. However, as the result of the
work of Stephen Cook, there is a surprising unifying theme that connects
all these problems. If you solve one of them, in the sense of finding a
polynomial-time algorithm, you’ve solved them all.
In the 1960s, the University of California, Berkeley was an exciting place
to be. Mario Savio was leading the Free Speech Movement in front of
Sproul Hall. I was putting the finishing touches on my thesis (although it
must be admitted that historians of this era usually neglect to mention
this seminal event). Finally, two assistant professors in mathematics and
computer science were to become famous: Theodore Kaczynski (later to
be known as the Unabomber) and Stephen Cook.
What Stephen Cook did was to connect a wide variety of problems (in-
cluding the schedule construction problem and the traveling salesman
problem) by means of a transformational technique. He discovered an
algorithm that, when applied to one of these problems, would change the
problem into the form of the other in polynomial time. So, if you could
solve the traveling salesman problem in polynomial time, you could trans-
form the schedule construction problem in polynomial time into a
traveling salesman problem, which you could also solve in polynomial
time.^3 Two successive polynomial-time algorithms (one for transforming
the first problem into the second, one for solving the second) comprise a
polynomial-time algorithm: for example, if one has a polynomial, such as
P(x) 2 x^2 3 x5, and we substitute another polynomial, such as x^3 3,
for x in that expression, the result—2(x^3 3)^2 3(x^3 3)5—is still a pol-
ynomial, though admittedly of higher degree.
This greatly raises the stakes for determining whether (or not) there is
a polynomial-time algorithm for schedule construction. If you can find
one, using Cook’s transformational methods, you will have polynomial-
time algorithms for more than a thousand other useful problems. You
will not only gain undying fame, you will also make lots of money by han-
dling all these problems for a fee—plus, you get to collect one of the Clay
Mathematics Institute Millennium Prizes of $1 million for finding such
an algorithm. If you can demonstrate that no such algorithm exists, you
Murphy’s Law 163