of them and in fact any problem in NP.
Steve Cook, Leonid Levin, and Richard
Karp10, 24, 27 developed the initial theory
of NP-completeness that generated
multiple ACM Turing Awards.
In the 1970s, theoretical computer scientists showed hundreds more
problems NP-complete (see Garey and
Johnson16). An efficient solution to any
NP-complete problem would imply P =
NP and an efficient solution to every NP-
Most computer scientists quickly
came to believe P ≠ NP and trying to
prove it quickly became the single most
important question in all of theoretical
computer science and one of the most
important in all of mathematics. Soon
the P versus NP problem became an important computational issue in nearly
every scientific discipline.
As computers grew cheaper and
more powerful, computation started
playing a major role in nearly every academic field, especially the sciences. The
more scientists can do with computers,
the more they realize some problems
seem computationally difficult. Many of
these fundamental problems turn out
to be NP-complete. A small sample:
Finding a DNA sequence that best ˲
fits a collection of fragments of the sequence (see Gusfield20).
Finding a ground state in the Ising ˲
model of phase transitions (see Cipra8).
Finding Nash Equilbriums with ˲
specific properties in a number of environments (see Conitzer9).
Finding optimal protein threading ˲
Determining if a mathematical ˲
statement has a short proof (follows
In 2000, the Clay Math Institute
named the P versus NP problem as one
of the seven most important open questions in mathematics and has offered a
million-dollar prize for a proof that determines whether or not P = NP.
What we would
gain from P = NP
will make the whole
internet look like a
footnote in history.
What if P = NP?
To understand the importance of the
P versus NP problem let us imagine
a world where P = NP. Technically we
could have P = NP, but not have practical algorithms for most NP-complete
problems. But suppose in fact we do
have very quick algorithms for all these
Many focus on the negative, that if
P = NP then public-key cryptography
becomes impossible. True, but what
we will gain from P = NP will make the
whole Internet look like a footnote in
Since all the NP-complete optimization problems become easy, everything
will be much more efficient. Transportation of all forms will be scheduled
optimally to move people and goods
around quicker and cheaper. Manufacturers can improve their production to
increase speed and create less waste.
And I’m just scratching the surface.
Learning becomes easy by using the
principle of Occam’s razor—we simply
find the smallest program consistent
with the data. Near perfect vision recognition, language comprehension and
translation and all other learning tasks
become trivial. We will also have much
better predictions of weather and earthquakes and other natural phenomenon.
P = NP would also have big implications in mathematics. One could find
short, fully logical proofs for theorems