What would happen if P equaled NP?

Many problems now believed intractable, from optimal scheduling to breaking cryptographic codes, would have efficient algorithms, and the act of finding solutions would be no harder than checking them. The effects on commerce, security, and science would be profound, which is part of why most experts expect P not to equal NP.

Why is the problem so hard to solve?

Proving P equals NP requires a fast algorithm for an NP-complete problem, which no one has found; proving they differ requires showing no such algorithm can exist. Results on relativization and natural proofs demonstrate that the standard techniques are inherently unable to establish the latter, so a genuinely new approach is needed.

The P versus NP Problem

The P versus NP problem asks whether every problem whose solutions can be verified quickly can also be solved quickly, the central open question of theoretical computer science and one of the Clay Millennium Prize problems.

Definition

P is the class of problems solvable in polynomial time, and NP the class of problems whose proposed solutions are verifiable in polynomial time; the P versus NP problem asks whether these two classes are equal, which holds if and only if some NP-complete problem is solvable in polynomial time.

Scope

This topic covers the formal statement of P versus NP, its equivalence to whether any NP-complete problem has a polynomial-time algorithm, the consequences of either answer, the barriers such as relativization, natural proofs, and algebrization that have blocked progress, and the widespread conjecture that the classes differ.

Core questions

Is finding a solution fundamentally harder than checking one?
Why does the answer hinge on whether any single NP-complete problem is in P?
What would the world look like if P equaled NP, and if it did not?
Why have decades of effort failed to resolve the question?

Key theories

Equivalence to NP-completeness: P equals NP if and only if any NP-complete problem has a polynomial-time algorithm, so the sweeping question reduces to the tractability of a single concrete problem such as satisfiability.
Proof barriers: Relativization, natural proofs, and algebrization results show that the main known proof techniques cannot settle P versus NP, explaining the difficulty and guiding the search for fundamentally new methods.

Clinical relevance

The presumed inequality of P and NP is the working assumption behind treating NP-hard problems as intractable and behind the security of cryptography, since efficient solving of NP problems would break widely used encryption; a constructive proof that P equals NP would transform optimization, logistics, and science.

History

Cook framed the question in 1971 alongside NP-completeness, and it was quickly recognized as fundamental. Attempts via circuit lower bounds in the 1980s met the natural-proofs barrier identified by Razborov and Rudich, and in 2000 the Clay Mathematics Institute named it a Millennium Prize problem with a one-million-dollar award.

Debates

Will P versus NP ever be resolved, and what is the answer?: Most researchers conjecture that P does not equal NP, but no proof exists and known techniques are provably insufficient. Opinions differ on whether resolution is near, requires radically new mathematics, or whether the question might even be independent of standard axioms.

Key figures

Stephen Cook
Leonid Levin
Richard Karp
Alexander Razborov

Seminal works

cook1971
aroraBarak2009

Frequently asked questions

What would happen if P equaled NP?: Many problems now believed intractable, from optimal scheduling to breaking cryptographic codes, would have efficient algorithms, and the act of finding solutions would be no harder than checking them. The effects on commerce, security, and science would be profound, which is part of why most experts expect P not to equal NP.
Why is the problem so hard to solve?: Proving P equals NP requires a fast algorithm for an NP-complete problem, which no one has found; proving they differ requires showing no such algorithm can exist. Results on relativization and natural proofs demonstrate that the standard techniques are inherently unable to establish the latter, so a genuinely new approach is needed.