review articles
Doi: 10.1145/1562164.1562186
It’s one of the fundamental mathematical
problems of our time, and its importance
grows with the rise of powerful computers.
BY LaNce foRTNoW
The Status of
the P versus
NP Problem
The software written for this illustration
makes a stylized version of a network graph
that draws connections between elements
based on proximity. The graph constantly
changes as the elements sort themselves.
wHEn Editor-in-CHiEF MosHE Vardi asked me to write
this piece for Communications, my first reaction was
the article could be written in two words:
Still open.
When I started graduate school in the mid-1980s,
many believed that the quickly developing area of
circuit complexity would soon settle the P versus
NP problem, whether every algorithmic problem
with efficiently verifiable solutions have efficiently
computable solutions. But circuit complexity and
other approaches to the problem have stalled and
we have little reason to believe we will see a proof
separating P from NP in the near future.
nevertheless, the computer science landscape
has dramatically changed in the nearly four decades
since Steve Cook presented his seminal NP-
completeness paper “The Complexity of Theorem-Proving Procedures” 10 in Shaker Heights, oH in early
May, 1971. Computational power has dramatically
increased, the cost of computing has
dramatically decreased, not to mention the power of the Internet. Computation has become a standard tool
in just about every academic field.
Whole subfields of biology, chemistry, physics, economics and others are
devoted to large-scale computational
modeling, simulations, and problem
solving.
As we solve larger and more complex problems with greater computational power and cleverer algorithms,
the problems we cannot tackle begin
to stand out. The theory of NP
-completeness helps us understand these
limitations and the P versus NP
problem begins to loom large not just as
an interesting theoretical question in
computer science, but as a basic principle that permeates all the sciences.
So while we don’t expect the P
versus NP problem to be resolved in the
near future, the question has driven
research in a number of topics to help
us understand, handle, and even take