Page 248 - Discrete Mathematics and Its Applications

3.3 Complexity of Algorithms 227

P VERSUS NP The study of the complexity of algorithms goes far beyond what we can
describe here. Note, however, that many solvable problems are believed to have the property
that no algorithm with polynomial worst-case time complexity solves them, but that a solution,
if known, can be checked in polynomial time. Problems for which a solution can be checked
in polynomial time are said to belong to the class NP (tractable problems are said to belong to
class P). The abbreviation NP stands for nondeterministic polynomial time. The satisfiability
problem, discussed in Section 1.3, is an example of an NP problem—we can quickly verify that
an assignment of truth values to the variables of a compound proposition makes it true, but no
polynomial time algorithm has been discovered for finding such an assignment of truth values.
n
(For example, an exhaustive search of all possible truth values requires (2 ) bit operations
where n is the number of variables in the compound proposition.)
There is also an important class of problems, called NP-complete problems, with the
property that if any of these problems can be solved by a polynomial worst-case time algorithm,
then all problems in the class NP can be solved by polynomial worst-case time algorithms.
The satisfiability problem, is also an example of an NP-complete problem. It is an NP problem
and if a polynomial time algorithm for solving it were known, there would be polynomial time
algorithms for all problems known to be in this class of problems (and there are many important
problems in this class). This last statement follows from the fact that every problem in NP
can be reduced in polynomial time to the satisfiability problem. Although more than 3000 NP-
complete problems are now known, the satisfiability problem was the first problem shown to be
NP-complete. The theorem that asserts this is known as the Cook-Levin theorem after Stephen
Cook and Leonid Levin, who independently proved it in the early 1970s.
The P versus NP problem asks whether NP, the class of problems for which it is possible
to check solutions in polynomial time, equals P, the class of tractable problems. If P=NP, there

would be some problems that cannot be solved in polynomial time, but whose solutions could
be verified in polynomial time. The concept of NP-completeness is helpful in research aimed
at solving the P versus NP problem, because NP-complete problems are the problems in NP
considered most likely not to be in P, as every problem in NP can be reduced to an NP-complete
problem in polynomial time. A large majority of theoretical computer scientists believe that
P = NP, which would mean that no NP-complete problem can be solved in polynomial time.
One reason for this belief is that despite extensive research, no one has succeeded in showing that
P = NP. In particular, no one has been able to find an algorithm with worst-case polynomial time
complexity that solves any NP-complete problem. The P versus NP problem is one of the most
famous unsolved problems in the mathematical sciences (which include theoretical computer
science). It is one of the seven famous Millennium Prize Problems, of which six remain unsolved.
A prize of $1,000,000 is offered by the Clay Mathematics Institute for its solution.

STEPHEN COOK (BORN 1939) Stephen Cook was born in Buffalo where his father worked as an industrial
chemist and taught university courses. His mother taught English courses in a community college. While in
high school Cook developed an interest in electronics through his work with a famous local inventor noted for
inventing the first implantable cardiac pacemaker.
Cook was a mathematics major at the University of Michigan, graduating in 1961. He did graduate work
at Harvard, receiving a master’s degree in 1962 and a Ph.D. in 1966. Cook was appointed an assistant professor
in the Mathematics Department at the University of California, Berkeley in 1966. He was not granted tenure
there, possibly because the members of the Mathematics Department did not find his work on what is now
considered to be one of the most important areas of theoretical computer science of sufficient interest. In 1970,
he joined the University of Toronto as an assistant professor, holding a joint appointment in the Computer
Science Department and the Mathematics Department. He has remained at the University of Toronto, where he was appointed a
University Professor in 1985.
Cook is considered to be one of the founders of computational complexity theory. His 1971 paper “The Complexity of Theorem
Proving Procedures” formalized the notions of NP-completeness and polynomial-time reduction, showed that NP-complete problems
exist by showing that the satisfiability problem is such a problem, and introduced the notorious P versus NP problem.
Cook has received many awards, including the 1982 Turing Award. He is married and has two sons. Among his interests are
playing the violin and racing sailboats.