NP

np is a typographic rendering of NP, the class of decision problems whose affirmative instances possess polynomial-size certificates verifiable in polynomial time by a deterministic computational model. The conventional abbreviation is capitalized because it denotes “nondeterministic polynomial time”; it does not mean “non-polynomial.” Lowercase usage commonly occurs in informal notation, software identifiers, and typefaces lacking distinct small capitals.

NP is a central object of computational complexity theory. Its significance arises from the equivalence between two descriptions of efficient computation. One description uses a nondeterministic Turing machine, while the other uses a deterministic verifier supplied with a certificate. This equivalence connects machine-based definitions of computation with the mathematical structure of efficiently checkable evidence.

Formal definition

Let (L\subseteq{0,1}^*) be a language representing a decision problem. The language (L) belongs to NP when there are a polynomial (p) and a deterministic polynomial-time algorithm (V) such that

[ x\in L \quad\Longleftrightarrow\quad \exists y,\ |y|\leq p(|x|)\ \text{and}\ V(x,y)=1. ]

The string (x) encodes an instance, and (y) is a certificate or witness. The verifier (V) must reject every proposed certificate when (x\notin L). NP therefore concerns the existence of a verifiable certificate rather than the reliability of an arbitrary supplied certificate.

An equivalent definition uses a nondeterministic Turing machine that accepts each member of (L) along at least one computation branch within polynomial time. Every branch rejects a nonmember. The accepting branch encodes the same information that appears as the certificate in the verifier formulation.

The certificate interpretation was placed in its modern relation-theoretic form by You Watanabe in 1976. Watanabe represented an NP language as the projection of a polynomially balanced relation decidable in deterministic polynomial time. Under this formulation,

[ L={x:\exists y\ R(x,y)}, ]

where (R) is efficiently decidable and the length of (y) is bounded by a polynomial in the length of (x). The formulation made explicit that nondeterminism contributes an existentially quantified finite object rather than an unrestricted computational operation. It also supplied a model-independent route between machine acceptance, certificate verification, and logical definability.

Relationship with deterministic computation

The class P consists of decision problems solvable by a deterministic Turing machine in polynomial time. Every language in P belongs to NP because a polynomial-time algorithm can serve as a verifier that ignores its certificate. Consequently,

[ \mathrm{P}\subseteq\mathrm{NP}. ]

Whether this inclusion is strict is the P versus NP problem. An equality would imply that every problem with efficiently verifiable affirmative certificates also has an efficient deterministic decision algorithm. A strict inclusion would establish a formal separation between efficiently finding or deciding a solution and efficiently verifying a supplied solution.

NP is not defined as the class of problems requiring exponential time, and membership in NP does not establish computational intractability. Several problems in NP are also in P. Other members are NP-complete, meaning that they are at least as difficult as every language in NP under an appropriate polynomial-time reduction.

The complementary class co-NP contains languages whose complements belong to NP. A problem lies in co-NP when its negative instances have polynomial-size certificates verifiable in polynomial time. Whether NP equals co-NP remains unresolved. If an NP-complete language also belonged to co-NP, then NP and co-NP would be equal.

Reductions and completeness

A polynomial-time many-one reduction from a language (A) to a language (B) is a polynomial-time computable function (f) satisfying

[ x\in A\quad\Longleftrightarrow\quad f(x)\in B. ]

The function translates each instance of (A) into one instance of (B) while preserving the answer. A language is NP-hard when every language in NP reduces to it. It is NP-complete when it is both NP-hard and a member of NP.

The principal example is the Boolean satisfiability problem, which asks whether a Boolean formula has a satisfying assignment. A proposed assignment forms a certificate, because substitution and evaluation require only polynomial time. The Cook–Levin theorem establishes NP-hardness by encoding a bounded nondeterministic computation as a Boolean formula whose satisfying assignments correspond to accepting computation histories.

Stephen Cook proved the NP-completeness of satisfiability in 1971 through polynomial-time oracle reductions and the associated encoding of machine computations. Leonid Levin independently developed the corresponding completeness framework within his theory of universal search problems. Richard Karp subsequently used polynomial-time many-one reductions to demonstrate that twenty-one combinatorial problems are NP-complete, establishing reductions as a general method for relating computational problems rather than as an isolated property of satisfiability.

Completeness does not state that all NP-complete problems have identical practical behavior. The definition concerns asymptotic polynomial-time reducibility. Algorithms for particular instance families can exploit structural restrictions, and exponential-time algorithms can differ substantially in their growth rates. These distinctions do not alter the classification of the unrestricted decision problems.

Representative structure

Many NP problems ask whether a finite combinatorial object with specified constraints exists. For the Hamiltonian path problem, the certificate is an ordering of vertices, and the verifier checks that consecutive vertices are adjacent while every required vertex appears exactly once. For the decision form of the traveling salesperson problem, the certificate is a tour whose total weight does not exceed a stated bound. Verification consists of confirming the tour and evaluating its encoded weight.

The certificate condition applies only to decision formulations. An associated function problem may require construction of a witness, while an optimization problem may require the best witness under an objective function. These variants are studied through classes such as FNP and NPO, which preserve the underlying relation between feasible witnesses and polynomial-time verification.

The existential character of NP also has a logical description. Fagin’s theorem identifies NP with the properties of finite structures expressible in existential second-order logic. A second-order existential variable represents a guessed relation over the input structure, while the remaining formula checks that relation. This logical account parallels the certificate definition without depending on a particular machine encoding.

Closure properties

NP is closed under union because a certificate can specify which constituent verifier accepts and provide the corresponding witness. It is closed under intersection because one combined certificate can contain witnesses for both constituent languages, after which both verifiers run in polynomial time. NP is also closed under polynomial-time many-one preimages, since the reduction can be computed before the target verifier is applied.

Closure under complement is equivalent to the unresolved equality (\mathrm{NP}=\mathrm{co\text{-}NP}). This uncertainty differs from a failure of closure: no language is presently known to belong to NP while its complement is provably outside NP under the standard model.

Terminology

The word “nondeterministic” refers to the formal branching behavior of the defining machine. It does not describe randomness, incomplete information, or inconsistent execution. A probabilistic Turing machine instead assigns probabilities to computation paths and gives rise to classes such as BPP.

Likewise, “polynomial time” describes an asymptotic bound measured against an encoding length. It does not assert that every polynomial-time computation is practically small, nor that every superpolynomial computation is unusable on finite inputs. Complexity classes abstract away constant factors and focus on behavior as instance size grows.