NP (complexity)

Lore & Background

NP is defined as the set of decision problems solvable in polynomial time by a nondeterministic Turing machine, or equivalently, verifiable in polynomial time by a deterministic Turing machine. These two definitions are equivalent because a nondeterministic Turing machine can guess a solution and then verify it deterministically. The complexity class P, problems solvable deterministically in polynomial time, is contained in NP, as a solution can be verified by solving the problem. It is widely believed, but not proven, that P is smaller than NP, meaning some problems have verifiable solutions but cannot be solved in polynomial time.

Reader's Guide

NP is a foundational complexity class that captures many important computational problems, such as the subset sum problem, where a proposed solution can be checked quickly even if finding it may be hard. The hardest problems in NP are called NP-complete; a polynomial-time algorithm for any NP-complete problem would imply a polynomial-time algorithm for all NP problems. The relationship between NP and co-NP, the class of problems with efficiently verifiable 'no' answers, remains an open question. The P versus NP problem, asking whether every problem with efficiently verifiable solutions can also be efficiently solved, is one of the most significant unsolved problems in computer science, with profound implications for cryptography, optimization, and artificial intelligence.

Did You Know?

• NP is closed under union, intersection, concatenation, Kleene star, and reversal, but it is not known whether it is closed under complement.
• The subset sum problem is in NP because a given subset can be verified to sum to zero in polynomial time.
• If P equals NP, then a polynomial-time algorithm would exist for solving NP-complete problems and, by corollary, all NP problems.
• The verifier-based definition of NP does not require an efficient verifier for 'no' answers; that class is called co-NP.

The Two Faces of NP: Nondeterminism Meets Verification

NP can be understood through two equivalent lenses. On one hand, it captures decision problems that a nondeterministic Turing machine can resolve within polynomial time. On the other, it describes problems where a yes answer comes with a proof that a deterministic machine can check in polynomial time. These two perspectives are not merely parallel—they are provably equivalent. The reason is that the nondeterministic algorithm naturally splits into two phases: first, a guess about the solution is generated in a nondeterministic fashion, and second, a deterministic procedure checks whether that guess actually solves the problem. The abbreviation NP itself is rooted in the first framing—nondeterministic, polynomial time. Formally, NP is the union over all natural numbers k of NTIME(n^k), meaning problems solvable by a nondeterministic machine in O(n^k) steps for some fixed k. Equivalently, a language L belongs to NP if there exist polynomials p and q, plus a deterministic verifier M, such that M runs in p(|x|) time on input (x, y), and for every x in L there is a string y of length q(|x|) that M accepts, while for every x not in L, no such y exists.

P Inside NP and the Crown of NP-Completeness

The class P—problems solvable deterministically in polynomial time—sits entirely inside NP. The inclusion is straightforward: if you can solve a problem in polynomial time, you can certainly verify a proposed solution in polynomial time by simply re-solving it. Yet the reverse direction remains one of the great unsolved questions in all of mathematics. It is widely believed, though never proven, that P is a strict subset of NP; that is, some decision problems have solutions that are easy to check but fundamentally hard to find. At the top of NP sit the NP-complete problems, the hardest members of the class. A polynomial-time algorithm for any single NP-complete problem would immediately yield polynomial-time algorithms for every problem in NP. Consequently, if P and NP were somehow equal, such an algorithm would exist for all NP-complete problems and, by extension, for the entirety of NP. The fact that no one has found such an algorithm, despite decades of effort, is what makes the P-versus-NP question so central to theoretical computer science.

Subset Sum and the Witness-Verifier Framework

A concrete example makes the verifier-based definition of NP feel tangible. Consider the subset sum problem: given a set of integers such as {−7, −3, −2, 5, 8}, determine whether some subset adds to zero. The answer here is yes, because {−3, −2, 5} sums to zero. A brute-force search over all subsets grows exponentially with the input size, making it impractical for large sets. However, if someone hands you a specific subset, you can add up its elements and confirm the sum in polynomial time. That subset acts as a witness—or certificate—proving the yes answer. An algorithm that performs this check is called a verifier (sometimes a certifier in the literature). This pattern generalizes: a decision problem Π is in NP if, for every instance I, there exists a witness W and a verifier V that, given the pair (I, W), returns yes in polynomial time when the witness is valid, or no otherwise. The framework does not demand an efficient way to find the witness, only an efficient way to confirm one when it is presented.

NP, co-NP, and the Unresolved Symmetry Question

The verifier-based definition of NP carries an important asymmetry: it only requires efficient verification of yes answers. The natural counterpart, co-NP, consists of decision problems where no answers can be verified in polynomial time. The subset sum example illustrates this neatly. The original question asks whether some subset sums to zero, and a witness is the subset itself. The complementary question—whether every non-empty subset has a nonzero sum—belongs to co-NP, because a no answer (meaning some subset does sum to zero) can be certified by exhibiting that subset. Whether NP and co-NP are actually the same class is an outstanding open problem in complexity theory. No one has been able to prove that every problem with efficiently verifiable yes answers also has efficiently verifiable no answers, or vice versa. This unresolved question sits alongside P versus NP as one of the fundamental boundaries defining the current frontier of what we understand about computational difficulty.