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