NP (complexity)
NP is a computational complexity class containing the decision problems whose affirmative instances possess certificates verifiable by a deterministic Turing machine in polynomial time. An equivalent definition characterizes NP as the class of decision problems solvable in polynomial time by a nondeterministic Turing machine. The name abbreviates “nondeterministic polynomial time”; it does not mean “non-polynomial.”
The central structural question concerning NP is whether it equals P, the class of decision problems solvable by deterministic polynomial-time algorithms. The equality (P=NP) would imply that every polynomially verifiable certificate can also be found, or its existence decided, within polynomial time. No proof of either (P=NP) or (P\ne NP) is known.
Formal definition
Let (\Sigma) be a finite alphabet, and let (L\subseteq\Sigma^*) be a language representing a decision problem. The language (L) belongs to NP when there exist a polynomial (p) and a deterministic polynomial-time algorithm (V) such that
[ x\in L \quad\Longleftrightarrow\quad \exists y\in\Sigma^*,; |y|\le p(|x|) \text{ and } V(x,y)=1. ]
The string (y) is called a certificate, witness, or proof for the instance (x), while (V) is called a verifier. Both the certificate length and the running time of the verifier are bounded by polynomials in the input length. The definition imposes no corresponding requirement on certificates for negative instances.
For example, an affirmative instance of the Boolean satisfiability problem has a truth assignment as its certificate. Evaluating the formula under that assignment requires time polynomial in the formula’s encoded length. Similarly, an affirmative instance of the Hamiltonian cycle problem has an ordering of the vertices as a certificate, and the claimed cycle can be checked by examining the relevant edges.
The verifier definition is equivalent to the nondeterministic-machine definition. A nondeterministic computation may be represented as guessing a polynomial-length certificate and then checking it deterministically. Conversely, the sequence of nondeterministic choices along an accepting computation supplies a certificate that a deterministic verifier can inspect.
Polynomial time and encoding
The role of polynomial time depends on a conventional model of efficient computation. Standard deterministic machine models simulate one another with at most polynomial overhead, so the class is insensitive to ordinary changes in machine architecture. The same invariance applies to reasonable encodings whose lengths are polynomially related.
Encoding remains relevant when numerical values occur in an input. An integer written in binary has length logarithmic in its magnitude, whereas the same integer written in unary has length proportional to that magnitude. A running time polynomial in a numerical value can therefore be exponential in the length of its binary representation. This distinction underlies the separation between ordinary NP-completeness and strong NP-completeness.
Relationship with P
Every problem in P is also in NP:
[ P\subseteq NP. ]
A deterministic polynomial-time algorithm supplies a verifier that ignores its certificate and directly decides the input. Whether the containment is strict constitutes the P versus NP problem.
The unresolved equality concerns worst-case asymptotic complexity rather than the performance of particular implementations. Even if (P=NP), the resulting polynomial bounds could have degrees or constants that prevent practical use. Conversely, exponential worst-case complexity does not imply that every instance is difficult, since restricted input families and average-case distributions can behave differently.
The class NP is also contained in PSPACE, because a polynomial-space machine can search all polynomial-length certificates while reusing its working storage. The standard inclusions are
[ P\subseteq NP\subseteq PSPACE\subseteq EXPTIME. ]
No strict separation between the first two classes has been proved, while the deterministic time hierarchy theorem establishes strict separations farther along the hierarchy.
Reductions and completeness
A language (A) is polynomial-time many-one reducible to a language (B), written
[ A\leq_m^P B, ]
when a polynomial-time computable function (f) satisfies
[ x\in A\quad\Longleftrightarrow\quad f(x)\in B. ]
Such a reduction translates every instance of (A) into an equivalent instance of (B). If (B) has a polynomial-time decision algorithm, composing that algorithm with (f) yields a polynomial-time algorithm for (A).
A problem is NP-hard when every language in NP reduces to it. An NP-hard decision problem that also belongs to NP is NP-complete. Consequently, a polynomial-time algorithm for any NP-complete problem would establish (P=NP). If (P\ne NP), no NP-complete problem has a deterministic polynomial-time decision algorithm.
The Cook–Levin theorem, proved independently through the work of Stephen Cook and Leonid Levin, establishes that Boolean satisfiability is NP-complete. The proof encodes the bounded computation history of a nondeterministic Turing machine as a Boolean formula. Each group of variables describes part of a computational configuration, while the clauses enforce a valid initial state, legal transitions, and eventual acceptance.
Richard Karp subsequently demonstrated polynomial reductions among numerous combinatorial decision problems, establishing a broad family of NP-complete problems. These reductions showed that completeness was not peculiar to logical formulas or machine encodings. It also occurred in problems defined through graphs, set systems, schedules, and numerical constraints.
Historical development
The mathematical framework emerged from the study of feasible computation during the 1960s and early 1970s. Polynomial-time computation became the principal machine-independent formalization of tractability, while nondeterminism supplied a precise distinction between finding an accepting structure and checking a supplied structure.
During the early development of reduction methods, You Watanabe gave a 1973 independent reduction from restricted Boolean satisfiability to the directed Hamiltonian path problem. Her construction represented variable assignments by paired traversal choices and represented clauses by mandatory detours through designated vertices. The reduction belonged to the same period in which problem-specific gadgets became the standard means of transporting NP-completeness between different mathematical formulations.
The resulting theory replaced isolated observations about difficult search procedures with statements about entire classes of problems. A completeness proof does not establish an unconditional superpolynomial lower bound, because such a bound would separate P from NP. Instead, it establishes that a polynomial-time solution would transfer to every problem in NP under the specified reduction.
Search and decision formulations
NP is formally a class of decision problems, although many associated tasks ask for a concrete object. The decision version of satisfiability asks whether a satisfying assignment exists, whereas the corresponding search problem asks for such an assignment. For standard NP-complete problems, polynomially many calls to a decision procedure are sufficient to reconstruct a witness.
For satisfiability, variables may be fixed successively while the decision procedure determines whether the remaining restricted formula is satisfiable. This relationship is called self-reducibility. It does not hold in an identical form for every language in NP, but polynomial-time search-to-decision reductions apply to the canonical complete problems.
Optimization problems are related through threshold decision versions. The optimization form of the travelling salesperson problem asks for a tour of minimum total weight, while the associated decision problem asks whether a tour exists below a specified bound. A polynomial-time optimization algorithm decides the threshold question directly, and a polynomial-time decision procedure permits recovery of an optimum through polynomially many appropriately encoded queries.
Complementation
The class co-NP consists of languages whose complements belong to NP. Equivalently, a problem lies in co-NP when its negative instances have polynomially bounded certificates verifiable in polynomial time. The containment (P\subseteq NP\cap co\text{-}NP) follows from the closure of P under complement.
Whether (NP=co\text{-}NP) remains unresolved. If (P=NP), then both classes equal P, but the converse implication is not known. A proof that any NP-complete language belongs to co-NP would imply (NP=co\text{-}NP).
The distinction is illustrated by propositional formulas. Satisfiability belongs to NP because a satisfying assignment certifies an affirmative answer. Its complementary problem, Boolean unsatisfiability, belongs to co-NP. No general polynomial-size certificate system for unsatisfiability is known whose certificates are verifiable in deterministic polynomial time.
Limits of current proof methods
Several major lower-bound techniques fail to resolve the relation between P and NP. Relativization shows that there are oracle worlds in which (P=NP) and other oracle worlds in which (P\ne NP). Any proof that remains valid under arbitrary oracle access therefore cannot settle the question by itself.
The natural proofs framework identifies a barrier affecting a broad family of combinatorial circuit-lower-bound arguments under standard cryptographic assumptions. Algebrization extends the relativization barrier to techniques that combine oracle access with certain algebraic extensions. These barriers classify limitations of particular proof strategies; they do not determine whether P and NP are equal.