Some algorithmic problems have an asymmetry: checking a supplied solution seems much easier than finding one. Given a list of vertices, checking that every pair is joined is straightforward. Finding a large such list may require choices that the checking procedure never has to make. Complexity theory gives precise language for this distinction, and reductions let us transfer the difficulty of one problem to another without confusing the two tasks.
Motivation
Suppose someone announces a fast algorithm for finding a large clique in an arbitrary graph. One way to assess the consequences is to translate a different search problem into a graph so that its solutions correspond to cliques. If the translation is efficient, the announced graph algorithm would also solve the original problem efficiently. The translation is the reduction, and the direction of the translation determines what the consequence actually is.
We will formulate the problems as yes-or-no decisions. CLIQUE asks whether a graph contains a clique of at least a specified size. This lets a reduction preserve a single truth value. Optimization and search remain relevant, but they require additional arguments: a decision algorithm does not literally print a clique just because the word clique occurs in its name.
The main construction begins with a Boolean formula presented as a conjunction of short clauses. Each clause asks for at least one true literal. We create a vertex for each occurrence of a possible literal choice and join mutually consistent choices from different clauses. A clique reaching every clause then expresses a globally consistent way to satisfy them all. The proof must establish both directions; showing only how satisfying assignments make cliques would permit false positive graph instances.
Definitions
A decision problem is represented by a language , a set of finite binary strings interpreted as its yes instances. Fix an explicit encoding of graphs, formulas and integers; malformed encodings are rejected. The input size is its encoding length, not the largest number named by the input. The class consists of languages decided by deterministic algorithms in time polynomial in , on a standard discrete bit model.
A language belongs to if there are a deterministic verifier and a polynomial bound such that
where verification takes polynomial time in for witnesses within that bound. The string is a certificate or witness. The equivalence requires a witness for each yes instance and forbids every accepting witness for a no instance. A short witness alone is insufficient if checking it takes exponential time. Polynomial time in an unrestricted, arbitrarily long witness would also be insufficient for the stated class.
A polynomial-time many-one reduction is a total function computable in polynomial time such that if and only if , for every input string . It translates inputs and preserves their yes-or-no answer. A language is NP-hard if every language in NP reduces to it. It is NP-complete if it is both NP-hard and a member of NP. Hardness alone does not establish membership.
In a finite simple undirected graph , a clique is a vertex subset whose distinct pairs are all edges. An independent set has no edge between any of its distinct members. A vertex cover is a subset meeting every edge. CLIQUE and INDEPENDENT SET ask whether a set of the corresponding kind has size at least ; VERTEX COVER asks for size at most a bound . We use nonnegative integer thresholds; trivial out-of-range cases can be decided directly.
Graphs are encoded with an explicit vertex list and edge list, or an adjacency matrix. In particular, even isolated vertices occupy space in the representation, so the vertex count is bounded by a polynomial in input length. A succinct encoding that names exponentially many isolated vertices using only a binary vertex count is a different input model and is not assumed in the reductions below.
A Boolean literal is a variable or its negation. A clause is a disjunction of literals, and a conjunctive normal form, or CNF, is a conjunction of clauses. Here 3SAT means satisfiability of CNF formulas whose clauses contain at most three literals. Clauses may have one or two literals; repeating a literal can pad them to exactly three if that alternative convention is desired. An empty clause makes a formula unsatisfiable, whereas a conjunction with no clauses is true.
Theorem/proposition
Theorem 13.1.1
(Reductions transport algorithms and compose)
If and , then . Polynomial-time many-one reductions are transitive. Consequently, if is NP-hard and , then is NP-hard. If also , then is NP-complete.
Theorem 13.1.2
(Three equivalent graph certificates)
Let have vertices and let be its simple complement: distinct vertices are adjacent there exactly when they are not adjacent in . For ,
These equivalences give polynomial-time reductions, and all three decision problems belong to NP.
Theorem 13.1.3
(Selecting compatible literals produces a clique reduction)
Given a 3CNF formula with nonempty clauses, create one vertex for each literal occurrence. Join two vertices exactly when they belong to different clauses and their literals are not a variable and its negation. The formula is satisfiable if and only if the resulting graph has a clique of size at least . The construction has at most vertices and polynomial encoding length and construction time.
Proof sketch or proof idea
Proof
(Reductions compose and transport algorithms)
To decide using a decider for , compute and run that decider on it. A polynomial-time translation can print only polynomially many output bits, so is polynomial in . A polynomial running time in is therefore still polynomial in . Composing two translations preserves the answer equivalence and the same length bound, proving transitivity. The NP-hardness implication follows by composing a reduction from any language in NP to with the given reduction from to .
Proof
(The three graph equivalences and their verifiers)
For the graph equivalences, every pair within a subset is an edge of exactly when every such pair is a nonedge of its complement. Also, for any graph , a set is independent exactly when is a vertex cover. Indeed, an uncovered edge would have both endpoints in , and such an edge is precisely a failure of independence. Complementing a vertex subset changes size to , which changes the lower threshold to the upper threshold . Constructing a graph complement takes pair checks in an adjacency-matrix representation.
To verify a clique, check that a supplied list contains at least distinct valid vertices and check every pair. An independent-set verifier checks the absence of those pair edges; a vertex-cover verifier scans all edges and checks that each has a listed endpoint and that the list size is at most the bound. Vertex lists have polynomial length, and each check is polynomial. Their membership proofs are independent of their hardness proofs.
Proof
(The clause-to-clique reduction)
Now take a satisfying assignment of the formula. Choose one true literal occurrence in each clause. Chosen vertices belong to different clauses, and no two chosen literals are complements because an assignment cannot make both true. All pairs are therefore edges, so these vertices form a clique.
Conversely, no two vertices of a clique can come from the same clause, since the construction places no edge within a clause. A clique has at most vertices. A clique of size at least therefore has exactly one occurrence from every clause. No chosen occurrences have complementary literals. Set each chosen positive variable to true and each chosen negative variable to false; pairwise consistency makes these instructions compatible even if a variable is selected several times. Give arbitrary values to variables never selected. Every clause has a selected true literal, so the whole formula is satisfied.
There are at most literal occurrences, so examining every pair is polynomial. A literal's variable name also occupies bits; construction time includes comparing those names and remains polynomial in the full formula encoding length. A formula with an empty clause can instead be mapped immediately to a fixed no CLIQUE instance, and an empty conjunction to a fixed yes instance. Malformed source strings likewise map to a fixed no instance. This makes the reduction total rather than leaving exceptional encodings undefined.
Proof X-ray
Both the missing edges and the present edges have jobs
Omitting edges within a clause forces a large clique to reach distinct clauses. Omitting edges between complementary literals makes the selected instructions consistent. The threshold then forces every clause to be represented. These are three separate obligations; a graph encoding that satisfies only two can accept formulas it was supposed to reject.
Proof
(Replacing SAT by clauses of at most three literals)
For completeness, why may SAT be replaced by 3SAT? Express a Boolean formula using binary AND and OR gates and unary NOT gates, and introduce a new variable for each internal gate value. For an AND gate , impose clauses , and . For an OR gate use , and . For a NOT gate , use and . Finally assert the output variable by a unit clause.
Each group enforces exactly the stated gate truth table. A satisfying original assignment extends by its actual gate values; a satisfying clause assignment, read in gate order, must agree with every gate and make the output true. The number of new variables and clauses is linear in the formula-tree size. Hence this is a polynomial satisfiability-preserving conversion to clauses of size at most three. Combined with the stated Cook–Levin theorem, it makes 3SAT NP-complete, and the proved graph reductions transfer NP-hardness to CLIQUE, INDEPENDENT SET and VERTEX COVER.
Worked examples
Worked example 13.1.4
(Reading an assignment from compatible choices)
Take . Its three clause groups contain six occurrence vertices. Choose in the first clause, in the second and in the third. They are mutually noncomplementary and hence form a three-clique. Their instructions give true, true and false, satisfying every clause. Choosing and from the first two clauses would fail because the corresponding vertices have no edge, regardless of the third choice.
Worked example 13.1.5
(Thresholds change when subsets are complemented)
Let be the four-vertex path with edges . The set is independent, and its complement is a vertex cover. In , the pair is a clique. Thus the CLIQUE instance maps to the independent-set instance and then to the vertex-cover instance . The graph complement changes adjacency; the subset complement changes the size threshold. They are different operations, even though this example uses both.
Worked example 13.1.6
(Why a numerical parameter can mislead a running-time claim)
The usual dynamic program for SUBSET SUM, on nonnegative integer items and target , records which sums from zero to are attainable and can use table updates. If , then its binary encoding uses only bits, while the table has entries. This algorithm is polynomial in the numerical value , but is not thereby polynomial in the binary input length. Such a bound is called pseudopolynomial. This observation explains the cost model; it is not a proof of SUBSET SUM's NP-hardness.
Common mistakes
Counterexample mode
Edges inside a clause would accept an unsatisfiable formula
A tempting variant also joins vertices from the same clause, on the grounds that extra edges only make large cliques easier to find. Apply it to the unsatisfiable formula , where . Two occurrences of in the first clause would then be adjacent and form a clique of size , although no assignment satisfies the formula. The construction as stated has no edge inside a clause precisely so that a clique of size must use every clause exactly once.
Common mistake
(Reducing in the wrong direction)
To prove a new problem hard, reduce a known hard problem to . A reduction to a known hard problem only supplies a way to solve if can be solved. Easy languages also reduce to many hard languages. The arrow alone expresses an algorithmic implication, not a symmetric comparison.
Common mistake
(Misreading the letters NP)
NP does not mean “not polynomial.” Every problem in P belongs to NP by a verifier that ignores an empty certificate and runs the decider, so NP-completeness does not prove that no polynomial-time algorithm exists. If any NP-complete language were in P, the reduction theorem would put every NP language in P; deciding whether that happens is the P versus NP problem. Nor is nondeterministic the same as randomized: the NP verifier is deterministic and the existential witness supplies the successful choice, while random sampling that fails to find a witness does not certify that none exists.
Common mistake
(Solving the source problem inside the reduction)
A reduction should transform input data without first solving the source problem. “Output a yes graph if the formula is satisfiable and a no graph otherwise” preserves the answer as a mathematical description, but no polynomial-time construction has been established. The compatible-occurrence construction succeeds because it builds the graph directly from local syntax.
Summary
NP formalizes polynomially bounded, efficiently checkable certificates. A many-one reduction translates every input in polynomial time and preserves both yes and no answers. Clause occurrences encode a satisfying assignment as a clique, and graph and subset complements transfer that certificate to independent sets and vertex covers. Membership, hardness and the foundational theorem used to begin the reduction chain remain separate proof obligations.
Exercises
Quick check
(Explain which reduction direction would let a polynomial-time algorithm for VERTEX COVER solve 3SAT, and identify the threshold after both graph reductions.)
Solution · Answer
Use . For a formula with nonempty clauses, its occurrence graph has vertices and clique threshold . In the complement graph the independent-set threshold is , and the final vertex-cover threshold is . Exceptional empty-clause and empty-conjunction inputs are decided and mapped to fixed instances as described in the construction.
Quick check
(In the clause-to-clique construction, suppose the edge between two vertices carrying complementary literals from different clauses were added. Give an unsatisfiable formula for which a false positive results.)
Solution · Answer
The formula is unsatisfiable, with . With the extra edge, the vertex in the first clause and the vertex in the second clause form a clique of size , so the graph is wrongly accepted. The missing complementary edge is what makes the chosen literals mutually consistent.
Quick check
(Give a polynomial certificate and verifier for the decision problem “Does this nonempty finite undirected graph have a simple path visiting every vertex exactly once?”)
Solution · Answer
Supply an ordered list of all vertices. Check that its length is the vertex count, that each valid vertex appears once, and that every consecutive pair is an edge. The list has bits under a standard vertex-label encoding, and the checks take polynomial time. A one-vertex graph has a path consisting of that vertex. This establishes membership in NP; it does not establish NP-hardness of this path problem.
Quick check
(Why does a fixed easy instance of an NP-complete problem not contradict NP-hardness? Distinguish instances from languages.)
Solution · Answer
NP-hardness quantifies over an entire family of arbitrary encoded inputs and polynomial algorithms for that family. One fixed graph can have its answer stored as a constant; special graph classes may also admit fast algorithms. Neither supplies a polynomial algorithm deciding every instance of the unrestricted NP-complete language.
Exercise 13.1.7
(Prove that if and , then .)
CoreProof
Solution(3)
- 1
Build a verifier for
On input and a witness , compute with the reduction, then run the verifier on .
- 2
Bound the witness and the running time
Key step
The reduction is polynomial, so is bounded by a polynomial in . Substituting it into the witness bound and verification time of gives polynomials in ; adding the time to compute keeps the total polynomial.
Because: The output-length bound is part of what a polynomial-time reduction provides.
- 3
Conclude membership
∎if and only if , if and only if some short witness is accepted by on . So the new verifier accepts a witness for exactly the members of , and .