A proposed solution can sometimes be checked much faster than it is found. Complexity theory formalizes this distinction with short certificates, and reductions transfer the difficulty of one decision problem to another. The direction of that transfer is essential: to show a target is hard, translate known hard instances into target instances.
This unit develops the three ideas that make that sentence precise. First, we define the classes NP and coNP through verifiers and discuss what a certificate can and cannot do. Second, we define polynomial-time many-one reductions and prove that they transport efficient algorithms and compose. Third, we use these tools in an NP-completeness argument from 3-SAT to CLIQUE, and we examine several tempting but invalid arguments. Throughout, "polynomial time" refers to deterministic Turing machines (or any equivalent model with polynomial overhead), and all languages are over a fixed finite alphabet, with instances encoded as strings in a reasonable way.
Motivation: finding versus checking
Consider a Sudoku grid of size . Given a completed grid, one checks every row, column, and block in time polynomial in the grid size. Producing a completed grid from a partially filled one appears to require exploring a vast space of possibilities, and no polynomial-time method is known for the generalized problem. The asymmetry between a cheap check and an apparently expensive search is the phenomenon that the class NP isolates.
The formalization needs care. A "solution" must be short enough to be read by a polynomial-time machine, since otherwise the check could not even inspect it. A "check" must be deterministic and efficient, and it must be sound: no false certificate can convince it that a no-instance is a yes-instance. These requirements appear explicitly in the definition below.
Certificates and reductions
Definition 2.1.1
(NP and coNP)
A language is in if there are a polynomial and a deterministic polynomial-time verifier such that exactly when some string of length at most satisfies . The class consists of complements of languages in . For a language in coNP, its no-instances have short NP certificates, since . This does not assert short NP certificates for its yes-instances. Every language in lies in both classes; whether is open.
For SAT the input is a Boolean formula and a witness is a truth assignment. Evaluating the formula checks the witness in polynomial time. A failed assignment, however, does not certify unsatisfiability: other assignments may work. This observation does not prove that unsatisfiability has no short certificate; that would settle a major open problem.
Reading the definition carefully
The definition has two quantifier patterns that should be kept apart. For there must exist a short with . For , every short must give . Written symbolically,
Negating this gives . The complement language is therefore described by a universal condition over short strings. This condition is not a single existential certificate. A language in instead has short, efficiently checkable certificates for both answers, through separate NP verifiers for it and its complement.
The inclusion holds because is closed under complement: swap the accepting and rejecting outcomes of a decider. Whether is also open. If some NP-complete language were in coNP, then would follow. This is a clean application of reductions: for , a reduction is also a reduction , and , so by the closure of NP under polynomial-time preimages proved below. Hence , and taking complements gives .
Definition 2.1.2
(Many-one reduction and completeness)
A polynomial-time many-one reduction is a polynomial-time computable function with if and only if . A language is NP-hard if every language in reduces to it in this sense. It is NP-complete if it is both NP-hard and in .
The "if and only if" is two implications, and both must be proved for each reduction. The forward implication () is called completeness of the reduction, and the backward implication () is called soundness; equivalently, . Forgetting either direction produces an invalid argument, as the counterexamples below show. The function must be total and computable in polynomial time on every string, including strings that are not well-formed instances; the standard convention is to map malformed inputs to a fixed string outside , provided is not the set of all strings.
Proposition 2.1.3
(Reduction transfers an efficient decision procedure)
If and , then . Polynomial-time many-one reductions are transitive.
Proof
(Compose the reduction with the decider)
On input , compute and run a polynomial-time decider for . The equivalence of membership makes the answer correct. The output length of is at most its running time, hence polynomial in ; composing the two polynomial bounds is polynomial. Transitivity follows by composing reduction functions and applying the same length bound.
The proposition is usually used in its contrapositive form: if and , then . Since no NP-complete language is currently known to lie outside , the practical reading is conditional: if is NP-hard and , then is NP-hard, and is in only if .
The companion units on verifier circuits and gate constraints prove the Cook–Levin construction and SAT/3-SAT NP-completeness: normalize a short witness, simulate the clocked verifier, and impose satisfiability-preserving local gate clauses. The following graph example uses their 3-SAT result as background. A 3-CNF formula is a conjunction of clauses, each containing three literal occurrences; repeated literals are allowed here. The companion also supplies gadgets for the distinct-variable convention.
A completeness proof
Every NP-completeness proof for a new language follows the same template, and it is worth stating before the example.
- Show by describing a certificate and a polynomial-time verifier.
- Choose a language already known to be NP-hard.
- Define a function and show it is computable in polynomial time.
- Prove .
- Prove .
Definition 2.1.4
(CLIQUE and the clause-occurrence graph)
CLIQUE consists of pairs where is a finite simple undirected graph with a set of pairwise adjacent vertices. Given a 3-CNF formula with clauses, create one vertex for each literal occurrence. Join vertices from different clauses exactly when their literals are not complementary. Set .
Theorem 2.1.5
(3-SAT reduces to CLIQUE)
For a 3-CNF formula with clauses, let be its clause-occurrence graph and set . Then is satisfiable if and only if has a -clique, and is computable in polynomial time. Since CLIQUE is in NP, CLIQUE is NP-complete.
Proof
(Both directions of the clique reduction)
A satisfying assignment selects one true occurrence from every clause. The selected vertices form a -clique: true literals cannot contradict each other. Conversely, a -clique contains at most one vertex per clause, so it has one per clause. Its literals contain no complementary pair; assign their variables to make all selected literals true and assign the rest arbitrarily. Every clause is satisfied. The graph and are built in polynomial time, establishing both directions of the reduction.
CLIQUE is in NP: a list of distinct vertices is a certificate, and all pairs can be checked for edges. Therefore the reduction from NP-complete 3-SAT proves CLIQUE NP-complete. A reduction from CLIQUE to 3-SAT would show the opposite transfer and would not by itself prove CLIQUE hard.
Proof X-ray
Why the clique argument works
Two details deserve explicit comment. First, vertices in the same clause are never adjacent, so a clique can use at most one literal occurrence from each clause. Since the target size is and there are exactly clauses, the pigeonhole principle forces exactly one vertex per clause. Without that restriction, a clique of size could use several vertices from one clause and omit another clause entirely, so it would not certify that every clause is satisfied. Second, "not complementary" is exactly the consistency condition: a set of literal occurrences can be made simultaneously true by one assignment if and only if it contains no pair . If the same literal occurs in two selected clauses, both are made true by the same assignment, which is why equal literals are joined.
The following interactive example uses a separate two-clause formula; compare its occurrence choices with the three-clause example below.
Worked example 2.1.6
(A concrete instance of the reduction)
Take with clauses, and write the occurrences as in clause 1; in clause 2; and in clause 3. There are vertices. Between different clauses, the edges are all pairs except complementary ones. Between clauses 1 and 2, the complementary pairs are (), , , , (), giving edges, namely . Between clauses 1 and 3 the complementary pairs are , so there are edges. Between clauses 2 and 3 the complementary pairs are , , , so there are edges. The graph has edges and .
The formula is satisfiable: take true and false. Clause 1 is true via , clause 2 via , and clause 3 via . The triple is a clique: is an edge (computed above), is not complementary ( versus ), and joins equal literals . Conversely, the triple is not a clique because is the complementary pair ; correspondingly, choosing from clause 1, from clause 2 and from clause 3 would demand both false and true. The reduction behaves as claimed on this instance.
Worked example 2.1.7
(An unsatisfiable formula yields no clique)
Take , so and , and the graph has vertices. Every literal of clause 1 is and every literal of clause 2 is , so all cross-clause pairs are complementary and no edge is drawn. A -clique needs at least one edge, so none exists, matching the unsatisfiability of . With the faulty rule that also joins complementary literals, all nine edges would appear; see the common mistakes below.
Invalid arguments and counterexamples
Because the direction of a reduction is easily confused, it is useful to see concretely how invalid arguments fail.
Common mistake
(Verification is not search)
The verifier must accept every yes-instance for at least one short witness and reject every witness for every no-instance. It need not find the witness. Checking a proposed solution efficiently does not currently imply a known efficient method for finding one.
Common mistake
(Reducing in the wrong direction)
Suppose one shows and concludes that CLIQUE is NP-hard. This does not follow. The existence of a translation from CLIQUE into 3-SAT shows only that CLIQUE is no harder than 3-SAT. Indeed every language in reduces to every language that contains at least one string and omits at least one string: if and , , set when the decider accepts and otherwise. In particular every language in reduces to SAT, yet this says nothing about its hardness.
Common mistake
(Proving only one direction of the equivalence)
In a faulty variant of the clique construction, join all vertices from different clauses, including complementary ones. A satisfying assignment still yields a -clique, but the unsatisfiable formula yields six vertices with every cross-clause pair adjacent. Since , any such pair is a -clique. The reverse implication fails, so this is not a reduction.
The last example shows concretely why "not complementary" appears in the edge rule: it is exactly what makes the converse direction true.
If SAT were in coNP, then NP and coNP would coincide. This is why SAT is not believed to lie in coNP: that would collapse two classes widely thought to be different. The belief is not a theorem, and no result here proves .
Together with the closure property stated below and transitivity, this implies that if is NP-complete and with , then is NP-complete. This is the precise sense in which a single established hard problem seeds an entire family of hard problems.
Counterexample mode
An easy source can reduce to SAT
The false claim is that by itself makes NP-hard. Take and map every input to the fixed unsatisfiable formula . This is a polynomial-time many-one reduction, because both membership statements are always false. Indeed, the language of all strings cannot reduce to the empty language: a yes-instance would need an image in the empty set. To establish hardness of a target, start from a known hard source and reduce it to the target.
For the graph problems here, vertices are explicitly encoded, and is a nonnegative integer in binary. A verifier first rejects larger than the vertex count, rather than attempting to read an impossibly long certificate. Malformed encodings are outside the languages.
Proposition 2.1.8
(NP is closed under polynomial-time preimages)
If and , then . Composing the reduction with a verifier proves the claim, with the polynomial output-length bound controlling certificate length.
Proof
(Composing the reduction with a verifier)
Let be the reduction and a verifier and bound for . Define . Since for some polynomial , certificates of length at most suffice, and runs in polynomial time because computing and running on an input of polynomial length both do. If then and some short is accepted; if then and every is rejected. So .
Worked example 2.1.9
(A large numeric threshold does not require a long witness)
An explicitly listed graph has five vertices, while its binary threshold encodes . It cannot contain a clique of that size. The verifier rejects after reading the threshold and vertex count, without requesting a thousand labels. If , a proposed list such as is rejected for repetition before edge checks. For it checks the three pairs. The certificate verifies a selected set; it does not assert that no larger clique exists.
Practice and solutions
Quick check
(Why is ?)
Start from the definition of a certificate.
Solution · Answer
A verifier may ignore its certificate and run the polynomial-time decider for the language. The empty certificate suffices on yes-instances.
Quick check
(A reduction maps to . What follows if has a polynomial-time decider, and what does not follow merely from being easy?)
Compute, then decide.
Solution · Answer
Compute the reduction and then decide ; this decides in polynomial time. An easy does not imply is easy: the reduction may reach only an easy subset of the instances of .
Quick check
(In the proof that NP is closed under polynomial-time preimages, why do certificates of length at most suffice?)
Bound the length of first.
Solution · Answer
The verifier is run on , and . Taking nondecreasing, which loses no generality, needs certificates of length at most .
Quick check
(In the reduction from 3-SAT to CLIQUE, a formula has clauses. State the number of vertices and the maximum possible number of edges, and compute the exact number of edges for .)
Count the complementary pairs.
Solution · Answer
There are vertices. Between two different clauses there are pairs, and there are pairs of clauses, so at most edges, attained when no complementary pair exists. For the given formula , so there are vertices and cross pairs. The complementary pairs are once and four times (), five in all, so there are edges. The assignment true, false satisfies the formula, and the vertices for and the first form a -clique.