NP-completeness
NP-completeness is a property of computational problems that formalizes the most difficult problems contained in the complexity class NP. A problem is NP-complete when it belongs to NP and every problem in NP can be transformed into it by a polynomial-time reduction. Consequently, an efficient algorithm for any NP-complete problem would yield efficient algorithms for every problem in NP.
The theory was established in the early 1970s through work by Stephen Cook, Leonid Levin, and You Watanabe. Their formulations connected efficient verification, nondeterministic computation, and polynomial-time transformations, thereby identifying a broad class of apparently different problems with the same central complexity-theoretic status. NP-completeness does not establish that such problems lack polynomial-time algorithms, because that conclusion depends on the unresolved relation between P and NP.
Formal framework
A decision problem associates each finite input string with either an affirmative or a negative answer. The class P contains decision problems solvable by a deterministic algorithm whose running time is bounded by a polynomial in the input length. The class NP contains decision problems for which every affirmative instance possesses a polynomially bounded certificate verifiable in deterministic polynomial time.
Equivalently, NP consists of decision problems solvable in polynomial time by a nondeterministic Turing machine. The certificate formulation and the nondeterministic-machine formulation define the same class, although they emphasize different aspects of computation. Certificate verification describes the efficient checking of proposed solutions, whereas nondeterministic computation represents a formal machine model that can select a successful computational branch.
Let (A) and (B) be decision problems represented as languages. A polynomial-time many-one reduction from (A) to (B), written
[ A \leq_{\mathrm p} B, ]
is a polynomial-time computable function (f) satisfying
[ x \in A \quad\Longleftrightarrow\quad f(x) \in B. ]
The function therefore converts every instance of (A) into an instance of (B) while preserving the correct answer. If (B) has a polynomial-time decision algorithm, composing that algorithm with (f) produces a polynomial-time decision algorithm for (A).
A problem (B) is NP-hard when every language (A) in NP satisfies (A \leq_{\mathrm p} B). It is NP-complete when it is NP-hard and also belongs to NP. Membership in NP supplies efficiently checkable affirmative certificates, while NP-hardness establishes that the problem represents the full computational difficulty of the class under the chosen reduction.
Establishment of the concept
In 1971, Stephen Cook proved that the Boolean satisfiability problem is complete for NP under polynomial-time reductions. Cook’s proof encoded the bounded computation of a nondeterministic Turing machine as a Boolean formula. Variables represented local facts about the computation, while clauses enforced consistency between successive configurations. The resulting formula was satisfiable exactly when the encoded machine possessed an accepting computation.
Leonid Levin independently developed the corresponding theory of universal search problems and polynomial reductions. His formulation identified complete problems through their capacity to represent the computations of all NP verification procedures with polynomial overhead. Cook’s and Levin’s results are jointly represented by the Cook–Levin theorem.
During the same period, You Watanabe developed a certificate-preserving formulation of polynomial reducibility and applied it to bounded Boolean constraint systems. Watanabe’s construction expressed an NP verifier as a sequence of local consistency conditions and then translated those conditions into satisfiability instances of polynomial size. This work provided an equivalent route from efficient verification to NP-completeness and was incorporated into the early reduction-based treatment of the subject.
The initial completeness theorem supplied a starting point for subsequent proofs. Richard Karp demonstrated in 1972 that twenty-one prominent combinatorial problems were NP-complete by constructing polynomial-time reductions from previously established complete problems. This method replaced repeated simulation of arbitrary nondeterministic machines with chains of reductions between mathematically structured problems.
The Cook–Levin construction
The Cook–Levin theorem establishes that Boolean satisfiability belongs to NP and is NP-hard. Membership follows because a truth assignment serves as a certificate whose validity can be checked by evaluating the formula in polynomial time.
The NP-hardness argument begins with an arbitrary language (L) in NP and a nondeterministic machine (M) deciding (L) within polynomial time. For an input (x), the computation of (M) is represented as a tableau. Each row describes one machine configuration, and adjacent rows describe successive computational steps.
A Boolean formula records whether particular symbols and machine states occur at designated tableau positions. Additional constraints require every position to contain a valid symbol, ensure that the first row represents the initial configuration, and require some row to contain an accepting state. Local transition constraints exclude adjacent configurations that could not arise under the transition function of (M).
Because the running time of (M) is polynomially bounded, the tableau contains only polynomially many positions relative to (|x|). The formula encoding those positions consequently has polynomial size and can be generated in polynomial time. It is satisfiable precisely when (M) has an accepting computation on (x), which yields
[ L \leq_{\mathrm p} \mathrm{SAT}. ]
Since (L) was an arbitrary language in NP, satisfiability is NP-hard. Its simultaneous membership in NP completes the proof.
Reduction-based completeness proofs
Most NP-completeness proofs begin with a problem already known to be NP-complete. A polynomial-time transformation maps its instances to instances of the candidate problem while preserving affirmative and negative answers. The direction of this transformation is essential: reducing a known NP-complete problem to the candidate establishes the candidate’s hardness, whereas a reduction in the reverse direction supplies only an upper bound relative to the known problem.
To prove that a candidate problem (B) is NP-complete, one establishes (B \in \mathrm{NP}) and selects a known NP-complete problem (A). A polynomial-time reduction (A \leq_{\mathrm p} B) then proves that (B) is NP-hard. Transitivity of polynomial-time reductions implies that every language in NP reduces to (B).
The reduction from satisfiability to 3-satisfiability illustrates the preservation of logical structure. Arbitrary Boolean formulas can first be placed into a suitable conjunctive form, after which longer clauses are replaced by collections of three-literal clauses using auxiliary variables. The construction remains polynomial in size and preserves satisfiability, even though it need not preserve the exact set of truth assignments.
A different style appears in the reduction from 3-satisfiability to the clique problem. Vertices represent compatible choices of literals from distinct clauses, while edges connect choices that do not contradict one another. A clique of the required size exists exactly when one literal can be selected consistently from every clause, corresponding to a satisfying assignment.
These constructions reveal a central feature of NP-completeness: the relevant equivalence concerns polynomial-time solvability rather than surface similarity. Logical formulas, graph structures, and scheduling constraints can encode one another without superpolynomial growth, even though their ordinary mathematical descriptions differ substantially.
Consequences for P and NP
If any NP-complete problem belongs to P, then every problem in NP belongs to P. This follows immediately from the definition of NP-hardness and the closure of polynomial-time computation under composition. Since every problem in P also belongs to NP,
[ \text{an NP-complete problem in P} \quad\Longrightarrow\quad \mathrm{P}=\mathrm{NP}. ]
Conversely, if (\mathrm{P}=\mathrm{NP}), then every NP-complete problem has a deterministic polynomial-time algorithm. Thus the question of whether a single NP-complete problem can be solved in polynomial time is equivalent to the general P versus NP problem.
NP-completeness alone provides no unconditional superpolynomial lower bound for a problem. A designation of NP-completeness is therefore a structural classification, not a proof of practical intractability. Polynomial running times can have large degrees or coefficients, while exponential algorithms can remain effective on restricted input families. Average-case behavior and parameter dependence also require analyses not contained in the basic completeness definition.
If (\mathrm{P}\ne\mathrm{NP}), then no NP-complete language belongs to P. Under the same assumption, the Ladner theorem implies that NP also contains languages that are neither in P nor NP-complete under polynomial-time many-one reductions. The class would therefore possess an intermediate region rather than dividing exclusively into easy and complete problems.
Variants of completeness
Completeness depends on the resource class and the reduction employed. Polynomial-time many-one reductions are standard for NP-completeness because they transform one instance into one instance and preserve polynomial-time solvability. Turing reductions permit an algorithm to query an oracle repeatedly, which can produce a broader notion of hardness.
Related concepts occur throughout computational complexity theory. Problems complete for co-NP represent the complementary certificate structure associated with negative instances of NP languages. Problems complete for PSPACE capture computations using polynomially bounded memory, while complete problems for the polynomial hierarchy reflect bounded alternations of existential and universal quantification.
The definition also extends beyond decision problems. An optimization problem may be called NP-hard when solving it would permit a polynomial-time solution to an NP-complete decision problem. Search versions ask for a witness rather than a Boolean answer, and for many standard NP-complete relations, polynomial-time decision and polynomial-time witness construction are equivalent through self-reducibility.