advantage of the hardness of various
In this article I look at how people
have tried to solve the P versus NP
problem as well as how this question
has shaped so much of the research in
computer science and beyond. I will
look at how to handle NP-complete
problems and the theory that has
developed from those approaches.
I show how a new type of “
interactive proof systems” led to limitations
of approximation algorithms and
consider whether quantum computing can solve NP-complete problems
(short answer: not likely). And I close
by describing a new long-term project
that will try to separate P from NP
using algebraic-geometric techniques.
ILLUs TRATIon By C. E. B. REAs
This article does not try to be totally
accurate or complete either technically or historically, but rather informally
describes the P versus NP problem
and the major directions in computer
science inspired by this question over
the past several decades.
What is the P versus NP Problem?
Suppose we have a large group of students that we need to pair up to work
on projects. We know which students
are compatible with each other and we
want to put them in compatible groups
of two. We could search all possible pairings but even for 40 students we would
have more than 300 billion trillion possible pairings.
In 1965, Jack Edmonds12 gave an efficient algorithm to solve this matching problem and suggested a formal
definition of “efficient computation”
(runs in time a fixed polynomial of the
input size). The class of problems with
efficient solutions would later become
known as P for “Polynomial Time.”
But many related problems do not
seem to have such an efficient algorithm. What if we wanted to make
groups of three students with each pair
of students in each group compatible
(Partition into Triangles)? What if we
wanted to find a large group of students
all of whom are compatible with each
other (Clique)? What if we wanted to
sit students around a large round table
with no incompatible students sitting
next to each other (Hamiltonian Cycle)?
What if we put the students into three
groups so that each student is in the
same group with only his or her compatibles (3-Coloring)?
All these problems have a similar
favor: Given a potential solution, for
example, a seating chart for the round
table, we can validate that solution efficiently. The collection of problems
that have efficiently verifiable solutions
is known as NP (for “Nondeterministic
Polynomial-Time,” if you have to ask).
So P = NP means that for every problem that has an efficiently verifiable
solution, we can find that solution efficiently as well.
We call the very hardest NP problems
(which include Partition into Triangles,
Clique, Hamiltonian Cycle and 3-Col-
oring) “NP-complete,” that is, given an
efficient algorithm for one of them, we
can find an efficient algorithm for all