Motivation
The graph reductions in this chapter begin with three-literal clauses. Why can such a restricted-looking input represent an arbitrary Boolean formula? Repeatedly applying distributive laws can produce an enormous equivalent conjunctive normal form. A polynomial reduction needs a different representation of intermediate results.
The central idea is to name the value of each subformula. Small clauses then enforce each local calculation, and one final clause requires the complete formula to be true. We will prove what assignments survive this transformation, including the role of fresh variables and short clauses.
Definitions
Definition 4.2.1
(Boolean formulas and assignments)
A Boolean formula is a finite rooted tree with variable or constant leaves, unary negation nodes, and binary conjunction or disjunction nodes. Its size is its number of nodes; a repeated subformula written twice occupies two subtrees. An assignment gives each occurring variable a Boolean value and evaluates the tree from leaves to root.
Definition 4.2.2
(Literals, clauses and 3-SAT)
A literal is a variable or its negation. A clause is a disjunction of literal occurrences, and a CNF formula is a conjunction of clauses. An empty clause is false; a conjunction of zero clauses is true. Our 3-SAT convention requires exactly three literal occurrences in each clause, permitting repeated variables and repeated literals. It matches the occurrence-based convention in the companion graph reduction.
Definition 4.2.3
(Fresh variables and the assignment-extension property)
Auxiliary variables are fresh: they are different from original variables and from auxiliaries assigned to other nodes or clauses. If uses original variables and auxiliaries , its assignment-extension property for a formula means that, for every assignment to ,
This is stronger than merely asserting that the two formulas are either both satisfiable or both unsatisfiable. It also states precisely how a satisfying target assignment projects back to the source variables. The larger formula need not be equivalent to the source for arbitrary independently chosen auxiliary values.
Theorem/proposition
Theorem 4.2.4
(Local gate clauses enforce the exact gate value)
The following clauses are equivalent to the indicated Boolean equality:
Naming every nonvariable node of a formula and asserting these equalities, or a unit clause for a constant node, gives exactly one auxiliary extension of each original assignment. Requiring the root label to be true then gives the assignment-extension property for the original formula.
Theorem 4.2.5
(A polynomial transformation to exactly three occurrences)
For a formula with nodes, the gate construction followed by short-clause padding produces an exact-three-occurrence CNF with at most clauses and the assignment-extension property. Alternatively, a nonempty clause of length can be replaced by clauses of length three using fresh variables, preserving the same property for its original variables. Empty clauses and an empty conjunction have the separate treatments below.
Theorem 4.2.6
(3-SAT completeness with the starting theorem explicit)
Exact-three-occurrence 3-SAT belongs to NP. The formula transformation is a polynomial-time many-one reduction from SAT to this version of 3-SAT. Consequently, assuming the standard NP-completeness of SAT, this 3-SAT problem is NP-complete. The computation-to-formula theorem establishing the SAT starting point is still an imported dependency, not proved by the transformations here.
The imported starting theorem is stated in Stephen Cook's official P versus NP description, section 2, page 5. The following constructions and proofs supply the formula-restriction step locally.
Proof sketch or proof idea
Enforce both directions of a gate equation
For each nonvariable node , introduce a variable . A variable leaf keeps its original label. A constant-one node has clause and a constant-zero node has clause . At each connective node use the indicated clauses, with its label as output and its child labels as inputs. Finally add the unit clause consisting of the root label. A formula that is just a variable has that variable as root label and needs only this last clause.
Proof
(Gate clauses compute the node values)
For an AND gate, the first two clauses say that forces . The third says that forces . Together they give exactly the conjunction value, rather than just one implication. For OR, the first two clauses force whenever either input is one, and the third prevents when both inputs are zero. For NOT, the two clauses rule out the two equal-value assignments, leaving precisely opposite values.
Given an original assignment, evaluate the tree and assign every its node value. This satisfies all gate and constant clauses. Conversely, induction from children to parent shows that every assignment satisfying those clauses must use these same node values. Hence the auxiliary extension is unique before the root assertion; after adding it, an extension exists exactly when the original root value is one. Restricting any satisfying target assignment therefore gives a satisfying original assignment, proving the reverse direction too.
Proof X-ray
Local consistency and global acceptance are separate conditions
Gate clauses describe a truthful evaluation, even when the final value is false. The root unit clause turns that evaluation into an accepting one. Freshness lets the evaluations of different nodes coexist without accidentally identifying unrelated values. The reverse implication uses every local equality, not an assumption that the auxiliary labels were honestly chosen by the person supplying the certificate.
Keep short clauses and long clauses under control
Every gate contributes at most three clauses of length at most three; each constant contributes one, and the output assertion adds one. There are at most nonvariable nodes, giving at most clauses. Replace a unit clause by and a binary clause by . Repeating a literal does not change the clause's value, introduces no variable and preserves the extension property. Every resulting clause has exactly three occurrences.
Concept lensCombinatorial
Gate clauses as forbidden rows
A clause on three distinct variables is false on exactly one of the eight assignments to them, so it forbids that one row. The equality holds on four of the eight rows of , so the other four must be forbidden. The clause forbids the row ; the clauses and together forbid the three rows , and . These four rows are exactly the inconsistent ones.
When the starting input is already CNF, a direct alternative handles each long clause. For with , introduce and use
Proof
(The clause chain preserves extendability)
If all original literals are false, the first clause forces , successive middle clauses force every later auxiliary to one, and the last clause fails. If at least one literal is true, set exactly when the first original literals are all false. The first clause holds by this rule. A middle clause with already holds; if , either its original literal is true or the next auxiliary is one. If the last auxiliary is one, the original true clause forces one of its last two literals to be true. Thus all clauses hold. There are two end clauses and middle clauses, giving clauses, including the empty middle family when .
Proof X-ray
Why the auxiliary variables mark a prefix of false literals
Each auxiliary acts as a flag meaning that the first original literals are all false. The first clause switches the flag on when and both fail; each middle clause passes the flag along unless the next original literal is true; the last clause demands a true literal among once the flag has reached . The direction from a false clause to unsatisfiability uses only that the flag is forced on all the way.
The non-obvious point is the choice of in the other direction. The flag must switch off exactly after the first true literal: setting every fails when the only true literal is , because then the last clause has false and both false. The proof closes by checking the three clause shapes separately, which is why the end clauses and the middle clauses are treated apart.
Use different auxiliaries for different source clauses, so their chosen extensions combine. Pad clauses of lengths one and two as above and keep length-three clauses. If any source clause is empty, the entire CNF is unsatisfiable; output the fixed contradiction . A conjunction of zero source clauses is satisfiable and may stay the empty target conjunction. These cases are part of the construction.
Check the reduction's size as well as its truth
Proof
(Polynomial size and membership in NP)
The gate construction never expands a subtree by distribution. It writes a constant number of clauses per node. With source bit length , label fresh variables by node indices and distinguish their names from consistently renamed original variables. Original names are copied only a constant number of times per occurrence; fresh indices use bits. The output therefore uses bits, and parsing, naming and writing it are polynomial-time operations. The direct CNF construction is likewise linear in the number of literal occurrences at the logical level, with a polynomial encoded length.
Malformed source strings are sent to the fixed contradiction, making the reduction total without solving satisfiability. Its extension property proves the required yes/no equivalence. For NP membership, a certificate gives one bit for every distinct target variable. There are at most as many such variables as literal occurrences. Parsing, checking certificate length and evaluating each clause take polynomial time in the encoded input. The empty target conjunction needs an empty certificate and is accepted. Membership and the reduction transport the stated SAT hardness to 3-SAT.
Worked examples
Worked example 4.2.7
(Evaluating one formula through its labels)
For , use labels , , . Their gate clauses number three, two and three respectively; the root unit adds one, giving nine clauses before and after padding. With , the unique gate extension is , satisfying the root. With , it is , which fails the root clause. No different auxiliary choice can repair that false source assignment.
Worked example 4.2.8
(Splitting a five-literal clause)
For , use , and . At , the first two clauses force and the final clause holds because . If also becomes zero, all five original literals are false, yet the same forced auxiliaries make the final clause false. No satisfying extension remains.
Worked example 4.2.9
(Short and empty clauses have explicit meanings)
The clause becomes ; becomes . An empty source clause is replaced at the formula level by the two contradictory clauses above, since it makes the entire conjunction false. A CNF with no clauses is true instead. Confusing an empty clause with an empty collection of clauses reverses the answer before any gadget is applied.
Worked example 4.2.10
(Extensions need not always be unique)
Split the four-literal clause into . If all four original variables are true, both values of work. This chain encoding preserves existence of an extension but can introduce several extensions. The full gate encoding has the stronger uniqueness property proved above. A satisfiability reduction alone does not promise to preserve the number of satisfying assignments.
Common mistakes
Counterexample mode
One-way gate constraints can admit a false source assignment
For , suppose the inner label is constrained only by . Keep the correct NOT clauses for outer label and assert . With , choosing satisfies all these weakened constraints although is false. The missing clause rules out this dishonest inner value. Each gate needs its complete equality constraint.
Common mistake
(Reusing fresh variables across gadgets)
Fresh variables cannot be reused across unrelated gadgets. Each source clause or gate needs its own auxiliaries, so that the extensions chosen for different gadgets are independent and can be combined.
Common mistake
(Distributing instead of naming subformulas)
A reduction needs a polynomial output bound. Direct distribution of produces one clause for each choice of one variable from each pair, hence clauses. That expansion does not establish a polynomial reduction; naming each subformula writes a constant number of clauses per node.
Common mistake
(Assuming three distinct variables)
Exactly three occurrences with repetition is the convention used here. Restrictions requiring three distinct variables need additional constructions and are not silently included.
Summary
Fresh node labels and complete local gate equalities describe a unique evaluation; the root assertion selects true evaluations. Repetition pads short clauses without changing meaning, and a chain splits a long disjunction while preserving existence of an extension. Polynomial encoding bounds and NP verification complete the SAT-to-3-SAT reduction. SAT's starting completeness theorem remains an explicit prerequisite.
Exercises
Quick check
(Prove the three OR-gate clauses enforce by considering separately and .)
The clauses are , and .
Solution · Answer
If , the first two clauses become and , forcing both inputs to zero; the third already holds. If , the first two hold and the third requires . These are precisely the cases in which equals the disjunction. Conversely those cases satisfy every clause.
Quick check
(Give an exactly-three-occurrence gate encoding of . Verify which original assignments extend to satisfying target assignments.)
Name the NOT node and assert at the root.
Solution · Answer
Use a fresh label and the clauses , and . At , satisfies them. At , the NOT clauses force , contradicting the output clause, so there is no extension. Repeated literals supply length three without altering either implication.
Exercise 4.2.11
(Write the chain for a six-literal clause. Prove that all-false original literals give a contradiction, and explain a satisfying extension when the source clause is true.)
Core
Solution(3)
- 1
Write the chain
, , and .
Because: gives auxiliaries and clauses.
- 2
Treat the all-false case
Key step
If all are false, the first clause forces , then the second forces , the third forces , and the last clause becomes . No extension satisfies the chain.
Because: Each clause forces the next auxiliary to one.
- 3
Treat the true-clause case
Set exactly when are all false. The first clause holds because whenever are false. A middle clause holds if ; if , either is true or are all false, which gives . If , then are false, so a true literal of the source clause is or and the last clause holds.
Quick check
(An encoding uses correct clauses for every gate but omits the root assertion. Does its satisfiability imply the original formula is satisfiable? Give a counterexample and explain why the clause bound alone cannot establish a correct reduction.)
Try .
Solution · Answer
No. For , every original assignment still has a truthful evaluation of all nodes, although the root is always zero. Without its unit clause the gate constraints are satisfiable, while the source is not. Polynomial size and semantic correctness are separate proof obligations; the root clause is needed for their desired connection.