Motivation
When a problem resists greedy methods and dynamic programming, that failure alone does not prove it difficult. A reduction gives a more precise comparison: an efficient solution to one problem would provide an efficient solution to another. NP-completeness organizes these comparisons around problems with short, efficiently checkable certificates. It is a statement about worst-case polynomial-time solvability, not a claim that every small instance is practically impossible.
The chapter uses binary strings as encodings and measures time in input bits. Graphs have explicit vertex lists and edge lists, so their encodings have length at least their number of vertices. Nonnegative integer thresholds are encoded in binary; a negative threshold field is treated as malformed. Malformed encodings can be rejected during parsing. These conventions matter when claiming a construction has polynomial output size.
Definitions
Definition 4.1.1
(Decision problems, P, and NP)
A decision problem is represented by a language of yes-inputs. It lies in P if a deterministic algorithm decides membership and halts in time polynomial in the input length on every input. It lies in NP if there exist a polynomial and a deterministic polynomial-time verifier such that
The string is a certificate. The verifier runs in polynomial time in its total input length, with the certificate-length bound ensuring a polynomial bound in for legal certificates.
Every P language belongs to NP: a verifier can ignore the certificate and run its decision algorithm. NP does not mean “not polynomial.” It includes easy problems, and its definition neither supplies an efficient method to find a certificate nor requires short certificates of no-instances. The equality P=NP remains unresolved, as recorded by the Clay Mathematics Institute.
Definition 4.1.2
(Many-one reduction and completeness)
A polynomial-time many-one reduction is a total polynomial-time computable function with if and only if for every input . A language is NP-hard if every language in NP reduces to it. It is NP-complete if it is NP-hard and itself belongs to NP.
The reduction function must be computable without already knowing whether is a yes-instance. The two directions of the equivalence preserve both yes and no answers. A map that turns every source instance into an easy yes-instance is not a valid reduction unless the source has no no-instances. Totality can be enforced by sending malformed source inputs to a fixed no-instance of the target.
Theorems
Theorem 4.1.3
(Transporting algorithms and hardness)
If and , then . Reductions are transitive. Therefore, if an NP-complete language reduces to and , then is NP-complete. If any NP-complete language is in P, then P=NP.
Theorem 4.1.4
(A concrete chain of NP-complete graph problems)
Assuming the standard NP-completeness of 3-SAT, each of the following decision problems is NP-complete: CLIQUE, asking for at least pairwise adjacent vertices; INDEPENDENT SET, asking for at least pairwise nonadjacent vertices; and VERTEX COVER, asking for at most vertices meeting every edge.
External dependency. The general computation-to-formula theorem and the NP-completeness of 3-SAT are used here, not proved. Stephen Cook's official problem description, section 2, states this starting result. The reductions below are proved completely; they do not replace the omitted computation-tableau proof. A 3-SAT instance is a conjunction of clauses with exactly three literal occurrences per clause, allowing repetition. A literal is a variable or its negation.
Proof sketch or proof idea
Proof
(Algorithm transport and transitivity)
To decide using a solver for , first compute , then run the solver on that output. If the reduction takes polynomial time, its output length is polynomial too, since writing each bit costs time. The solver's polynomial in that output length is consequently a polynomial in . The defining equivalence gives the correct answer. This proves the first assertion.
For transitivity, compose the reduction functions. The same output-length argument bounds the second function's time, so the composition is polynomial and preserves the equivalence. If every NP language reduces to and reduces to , transitivity makes NP-hard; membership in NP supplies the remaining requirement. Finally, an NP-complete language in P would place every NP language in P by algorithm transport. Together with P contained in NP, this gives equality.
Notice the direction: to prove a new target hard, reduce a known hard source to that target. Reducing the target to an already hard problem shows only that a solver for the hard problem could solve the target. Easy problems can also reduce to hard ones, so that direction proves no hardness of the target.
From 3-SAT to CLIQUE
Let the formula have clauses. Make one graph vertex for each literal occurrence, retaining both the clause index and position, for vertices. Join two vertices exactly when they belong to different clauses and their literals are not complementary: one must not be a variable and the other its negation. Do not put edges within a clause. Set the requested clique size to .
Proof
(Satisfying assignments correspond to cliques of size )
If the formula is satisfiable, choose one true occurrence from each clause. Any two chosen literals are simultaneously true, so cannot be complementary; they also come from different clauses. All chosen vertices are adjacent, giving a clique of size .
Conversely, a clique has at most one vertex from each clause because same-clause vertices have no edge. A clique of at least vertices must therefore have exactly one from every clause. Its selected literals contain no complementary pair. Assign their variables the values making them true, consistently, and assign other variables arbitrarily. Every clause has its chosen true literal, so the formula is satisfied. Both directions are now established, rather than merely drawing a suggestive graph.
There are vertices and at most a quadratic number of candidate edges. Testing whether two literal names are complementary takes polynomial time in their encoded lengths, so writing the entire graph is polynomial in the formula length. If the formula has no clauses, the empty conjunction is true; send it to a fixed yes-instance, such as a one-vertex graph with threshold one. Malformed formulas go to a fixed no-instance. These boundary choices make the reduction total.
CLIQUE is in NP: if , reject immediately, without attempting to read a length- witness. Otherwise a certificate lists distinct vertices; checking distinctness and every pair's adjacency takes polynomial time and certificate length. A clique of size greater than contains one of size exactly , so this certificate matches the “at least” formulation. Combining membership with the reduction proves NP-completeness, conditional only on the stated 3-SAT starting theorem.
Proof X-ray
Why two edge rules are both needed
The graph has two edge rules, and each does one job. Having no edges inside a clause caps a clique at one vertex per clause, so a clique of size must take exactly one occurrence from every clause; that is what turns a clique into a choice of one literal for each clause. Having no edge between complementary literals makes the chosen literals consistent, so they can be made true by a single assignment.
Neither rule can be dropped. If edges inside a clause were allowed, a clique of size could take several occurrences from one clause and none from another, leaving that clause unsatisfied. If complementary literals were joined, a clique could contain both and , and no assignment makes both true. Two occurrences of the same literal in different clauses are adjacent, which is harmless: choosing both is consistent. The proof closes by setting the chosen literals true and giving every other variable an arbitrary value.
Complementary graph and complementary vertex set
The complement graph has the same vertices and an edge between distinct vertices exactly when does not. A vertex subset is a clique in exactly when it is independent in . The map therefore reduces CLIQUE to INDEPENDENT SET. With explicit vertices, constructing at most quadratically many edges is polynomial. Membership in NP is checked by listing the vertices and verifying that no chosen pair is adjacent.
Proof
(Independent sets and vertex covers are complements)
In the same graph, a subset is independent exactly when is a vertex cover. If is independent, an edge cannot have both endpoints in , so at least one endpoint belongs to its complement. Conversely, if the complement covers all edges, no edge can have both endpoints in . Thus, for ,
This gives the reduction . If , the source is no and can be sent to the fixed no-instance consisting of one edge with cover budget zero. A vertex-cover certificate lists at most the budget number of vertices and checks every edge for a listed endpoint. If the budget is at least , the answer is automatically yes. Thus certificates remain polynomial even when the numeric budget is large. This completes membership and hardness for VERTEX COVER.
The two uses of “complement” are different: one changes the graph's edges, and the other changes a chosen subset while keeping the graph. Writing these operations separately prevents a common incorrect reduction.
Decision, search, and optimization
A decision oracle answers yes or no, while a search problem asks for a witness. For CLIQUE, a decision solver can find a clique with polynomially many calls. First ask whether size is possible. If yes and , inspect a vertex . If deleting leaves a size- clique, delete it and continue. Otherwise every size- clique uses ; output and restrict to its neighbors, reducing the required size by one. In the latter case its remaining clique vertices must all be neighbors of . Each step removes at least one vertex or reduces the requested size, preserving a yes-instance, so there are at most a polynomial number of calls on no-larger graphs.
This procedure is an adaptive oracle algorithm, not the single-instance many-one reduction defined earlier. Its role is different: it shows how a hypothetical polynomial decision algorithm would yield a polynomial search algorithm for this problem. To find the maximum clique size, binary-search the monotone decision threshold between zero and , then reconstruct a clique at that threshold. These implications need proofs; the words “decision” and “optimization” are not interchangeable by definition.
Worked examples
Worked example 4.1.5
(Selecting consistent literal occurrences)
Take clauses and . There are six occurrence vertices, including separate vertices for repeated and . The assignment selects the first clause's occurrence and the second clause's occurrence, which form an edge. Selecting and instead gives no edge. Repeated names do not merge vertices because clause membership is part of the construction.
Worked example 4.1.6
(An independent set and its cover)
On a four-vertex path with edges , the set is independent. Its complement covers every edge. The set is not independent because edge is internal; its complement fails to cover that edge. This verifies both sides of the subset-complement equivalence on explicit feasible and infeasible choices.
Worked example 4.1.7
(Why a pseudopolynomial table does not settle P versus NP)
The knapsack table from the preceding chapter has a state for each numeric capacity. A binary capacity with bits may be close to , so can be exponential in the input length. Finding this table does not automatically give a polynomial-time algorithm for the binary decision problem. The resolution is the encoding distinction, not an inconsistency between dynamic programming and hardness reductions.
Common mistakes
Counterexample mode
An easy source does not make its target easy
Claim: if and CLIQUE is NP-complete, then is NP-hard. Take . The map sending every input to the fixed graph with one vertex and threshold , which is a no-instance of CLIQUE, is a polynomial-time many-one reduction . But is not NP-hard: NP contains the language of all strings, and a reduction from it to would need for every , which is impossible. The arrow carries algorithmic usefulness backward: a fast target solver helps the source, while a fast source solver does not solve arbitrary target inputs. To prove hardness, reduce a known hard problem to the target.
Common mistake
(Leaving a requirement out of an NP-completeness proof)
A hardness proof requires an explicit map, polynomial construction and output bounds, both directions of correctness, and a known hard starting problem. An NP-completeness proof additionally needs membership in NP. Listing a plausible certificate without a polynomial length bound leaves a gap.
Common mistake
(Reading more into NP-completeness than it says)
Do not infer that every NP problem is NP-complete, that NP-hard implies membership in NP, or that NP-completeness proves P differs from NP. It establishes the conditional consequence that a polynomial solver would make P=NP. It also gives no automatic exponential lower bound and no guarantee that a particular real-world instance is difficult. Approximation quality and special graph classes require separate analysis.
Summary
NP describes bounded verification, while reductions transfer hypothetical algorithms and hardness. The complete chain from 3-SAT to CLIQUE, graph-complement INDEPENDENT SET, and set-complement VERTEX COVER shows each proof obligation explicitly. The computation-to-formula theorem remains an acknowledged dependency; no omitted general proof or unresolved lower bound is presented as established here.
Exercises
Quick check
(A student proves where is NP-complete and claims is NP-hard. Explain the gap using an easy source language.)
Ask which problem a solver for which problem would help.
Solution · Answer
The reduction transports a solver for to , so it does not prove difficult. For example, the empty language reduces to CLIQUE by always outputting a fixed no-instance, yet the empty language is decidable immediately. To prove hardness, reduce a known NP-hard language into instead.
Exercise 4.1.8
(Show that CLIQUE remains in NP when the threshold is written in binary, including thresholds exceeding the vertex count.)
CoreProof
Solution(4)
- 1
Parse and compare the threshold
Parse the binary threshold and compare it with the vertex count in polynomial time. If , reject; no certificate is needed.
Because: Both numbers are written in the input.
- 2
Define the certificate
Key step
For , the certificate lists distinct vertex indices, which takes bits. For the empty certificate is valid.
Because: For the list is short.
- 3
Check the certificate
Distinctness and the pairwise adjacency of the listed vertices are checked in polynomial time.
- 4
Match the certificate to the decision question
∎A clique of size greater than contains a clique of size exactly , so an accepting certificate exists exactly when the graph has a clique of at least vertices.
Quick check
(For , describe the reduction graph and explain why it has no size-two clique.)
Check which pairs of occurrences are joined.
Solution · Answer
There are three occurrence vertices in each clause and no within-clause edges. Every cross-clause pair is complementary, so no cross edge is present either. The graph is six isolated vertices, and no two form a clique. The formula is indeed unsatisfiable, since it requires both and its negation to be true.
Exercise 4.1.9
(Prove that if and , then .)
CoreProof
Solution(3)
- 1
Apply the reduction
Let be the reduction. On input , compute in polynomial time; its length is at most for some polynomial .
- 2
Reuse the verifier of
Key step
Let (taken nondecreasing) and be a certificate bound and verifier for . Define and accept only certificates with ; this bound is at most , a polynomial in .
Because: The certificate bound of is applied to the image , whose length is polynomial in .
- 3
Check correctness and running time
∎The verifier runs in polynomial time. By the reduction equivalence, exactly when , exactly when some certificate with makes accept, which is exactly when some short makes accept. Hence .