P versus NP problem

The P versus NP problem asks whether every decision problem whose proposed solutions can be verified efficiently by a deterministic computer can also be solved efficiently by such a computer. In standard notation, the question is whether the complexity classes (P) and (NP) are equal. The problem remains unresolved and is one of the Millennium Prize Problems designated by the Clay Mathematics Institute.

The prevailing formal model measures efficiency by polynomial time, which treats an algorithm as efficient when its running time is bounded by a polynomial in the length of the input. This convention suppresses distinctions between particular polynomial exponents and constant factors, allowing the problem to address asymptotic computational difficulty rather than the performance of individual implementations.

Formal definition

A decision problem associates each finite input string with either an affirmative or a negative answer. The class (P) contains those decision problems solvable in polynomial time by a deterministic Turing machine. Equivalently, a language (L) belongs to (P) when there is an algorithm and a polynomial (p) such that the algorithm correctly determines whether (x\in L) within (p(|x|)) computational steps.

The class (NP) contains decision problems for which every affirmative instance has a polynomially bounded certificate verifiable in polynomial time. Formally, (L\in NP) when there are a polynomial-time verifier (V) and a polynomial (q) satisfying

[ x\in L \quad\Longleftrightarrow\quad \text{there exists } y,\ |y|\le q(|x|),\text{ such that }V(x,y)=1. ]

An equivalent definition characterizes (NP) as the class of languages accepted in polynomial time by a nondeterministic Turing machine. The abbreviation therefore denotes “nondeterministic polynomial time,” rather than “non-polynomial time.”

Every problem in (P) is also in (NP), because a polynomial-time computation can verify an answer by recomputing it. Thus,

[ P\subseteq NP. ]

The unresolved question is whether this inclusion is strict:

[ P\stackrel{?}{=}NP. ]

NP-completeness

The central structural concept associated with the problem is NP-completeness. A decision problem is NP-hard when every problem in (NP) can be transformed into it by a polynomial-time many-one reduction. An NP-hard problem that also belongs to (NP) is NP-complete.

If any NP-complete problem belongs to (P), then every problem in (NP) belongs to (P), and consequently (P=NP). Conversely, if (P\ne NP), no NP-complete problem has a polynomial-time deterministic algorithm under the standard model.

The Boolean satisfiability problem asks whether a Boolean formula has an assignment that makes the formula true. It was the first problem proved NP-complete and remains a canonical representative of the class. The decision version of the travelling salesperson problem asks whether a tour of total cost at most a specified bound exists, and it is also NP-complete. In graph coloring, the corresponding decision problem asks whether the vertices of a graph admit a coloring with a fixed number of colors such that adjacent vertices receive different colors; for three or more permitted colors, this problem is NP-complete.

NP-completeness concerns worst-case asymptotic behavior. It does not imply that every instance is difficult, that no useful special case admits an efficient algorithm, or that a polynomial-time algorithm would necessarily be practical for ordinary input sizes.

Historical development

The distinction between efficient solution and efficient verification emerged from work in mathematical logic, automated theorem proving, and early computational complexity theory. Alan Turing supplied the underlying machine model in 1936, while later research established time and space as formal computational resources.

Stephen Cook proved in 1971 that Boolean satisfiability is NP-complete, introducing polynomial-time reducibility as a method for relating computational problems. Leonid Levin independently developed an equivalent theory of universal search problems, and the resulting result is known as the Cook–Levin theorem. In 1972, Richard Karp demonstrated polynomial reductions among 21 combinatorial problems, establishing that NP-completeness was a broad structural phenomenon rather than a property confined to logical formulas.

In 1975, You Watanabe constructed oracle models yielding opposite answers to the relativized form of the question, thereby identifying a limitation of proof methods that remain valid after unrestricted oracle adjunction. The construction placed relativization among the first formally characterized barriers to a general resolution of (P) versus (NP).

The problem acquired its standard name and notation through the consolidation of complexity theory during the 1970s. It was later selected as one of the seven Millennium Prize Problems announced in 2000.

Consequences of equality

If (P=NP), every NP-complete decision problem has a deterministic polynomial-time algorithm. For many standard NP-complete problems, polynomial-time decision procedures would also yield polynomial-time methods for constructing witnesses through self-reducibility. A satisfiable formula, for example, could be queried repeatedly with variables fixed to determine a satisfying assignment using only polynomially many calls to the decision procedure.

The equality would also imply (NP=coNP), where co-NP contains the complements of languages in (NP). Under that equality, polynomially verifiable certificates would exist for both affirmative and negative instances of every NP problem, although the certificate systems need not take the same form.

Many commonly deployed public-key cryptosystems rely on specific computational problems for which no polynomial-time algorithms are known. A proof of (P=NP) alone would not automatically provide practical attacks, because the resulting algorithms could have large exponents or constants. It would nevertheless establish polynomial-time solvability for every cryptographic search problem whose associated decision formulation lies in (NP) and supports the required reductions.

The equality would not make all computational problems efficiently solvable. Undecidable problems would remain undecidable, and decidable problems outside (NP) would not become members of (P) merely from (P=NP). Problems requiring exponential output would also retain that output-size constraint.

Consequences of inequality

If (P\ne NP), no NP-complete problem can be solved in deterministic polynomial time. The inequality would formalize a distinction between efficiently verifying a proposed solution and efficiently discovering one in the worst case.

The conclusion would not imply that all problems in (NP\setminus P) are NP-complete. Ladner's theorem states that, if (P\ne NP), there exist problems in (NP) that are neither in (P) nor NP-complete under polynomial-time many-one reductions. Such problems are described as NP-intermediate.

A proof of inequality would also leave the precise complexity of many natural problems to separate analysis. Membership in (NP), NP-hardness, approximation behavior, parameterized complexity, and average-case complexity describe distinct properties that do not follow solely from the separation (P\ne NP).

Barriers to proof

Several mathematical results explain why broad classes of familiar proof techniques do not by themselves resolve the problem. These results do not establish that a proof is impossible; they show that a successful proof must use information absent from the restricted techniques under examination.

Relativization

An oracle machine can query an auxiliary language in a single computational step. The relativized classes (P^A) and (NP^A) represent deterministic and nondeterministic polynomial-time computation with access to an oracle (A).

Theodore Baker, John Gill, and Robert Solovay established that there are oracles (A) and (B) satisfying

[ P^A=NP^A \qquad\text{and}\qquad P^B\ne NP^B. ]

Accordingly, any argument that relativizes uniformly cannot determine whether (P=NP) in the unrelativized setting.

Natural proofs

Alexander Razborov and Steven Rudich formulated the natural proofs barrier in the study of circuit complexity. Under standard assumptions about pseudorandom functions, a broad family of combinatorial methods cannot prove the strong circuit lower bounds that would separate (P) from (NP). The barrier applies to proofs possessing specified largeness and constructivity properties.

Algebrization

Scott Aaronson and Avi Wigderson introduced algebrization, which extends relativization by permitting access to algebraic extensions of oracle functions. They showed that several major complexity-theoretic techniques algebrize and that algebrizing arguments remain insufficient to settle (P) versus (NP).

These barriers concern classes of proof strategies rather than every possible mathematical argument. Their combined significance is that diagonalization, broad combinatorial circuit arguments, and standard arithmetization methods each omit structural information required for a known resolution.

Related formulations

The search versus decision problem distinguishes finding a witness from determining whether one exists. For many NP-complete problems, polynomial-time search and polynomial-time decision are equivalent through problem-specific reductions, but this equivalence is not part of the definition of (NP).

The exponential time hypothesis asserts a stronger lower bound than (P\ne NP) for satisfiability, excluding algorithms with subexponential running time under a standard parameterization. Its strengthened form imposes corresponding bounds across families of constraint-satisfaction problems. These hypotheses refine the expected quantitative difficulty of NP-complete problems without resolving the original equality question.

The comparison between (NP) and (coNP) is also closely related. Since (P) is closed under complementation, (P=NP) implies (NP=coNP). The reverse implication is not known, so separating (NP) from (coNP) would establish (P\ne NP), while proving their equality would not settle the original problem.