Motivation
A polynomial-size circuit may reuse one intermediate answer many times. An ordinary formula is a tree: if we substitute the full expression for every reused answer, we may duplicate more and more work. This is the remaining obstacle between the verifier circuit in the preceding unit and a small satisfiability formula. The solution is to name each intermediate value and impose a short constraint saying what that name means.
Auxiliary variables do not have to preserve the original expression under every arbitrary assignment to the new names. They must preserve the existence of a consistent extension. That distinction is central to reductions. We will first encode gates, then split long clauses into three-literal clauses, tracking the existential quantifier over every new variable. Together with the preceding construction, this proves the Cook–Levin conclusions for SAT and 3-SAT rather than merely citing them.
Definitions
Definition 2.3.1
(Literals, clauses and the languages SAT and 3-SAT)
A literal is a variable or its negation. A clause is a disjunction of literals; a formula in conjunctive normal form, or CNF, is a conjunction of clauses. A three-CNF formula here has exactly three literal occurrences in each clause, with repetition allowed. Thus is permitted. A convention requiring three distinct underlying variables needs additional short-clause gadgets, supplied below; literal repetition alone does not meet that different convention.
We define SAT for explicitly encoded Boolean formulas using AND, OR, NOT and constants. We define 3-SAT using the three-CNF convention just stated. Malformed strings are no-instances. Both languages are in NP because an assignment has length at most the explicit description and can be checked by evaluating the formula. The empty conjunction is true and an empty clause is false; we will handle those cases when giving a total reduction.
Definition 2.3.2
(Equisatisfiability)
Two formulas and are equisatisfiable if one has some satisfying assignment exactly when the other does. Our transformations prove the stronger per-input statement
This does not say for every choice of . The new variables represent consistent intermediate values, not extra arbitrary permissions to accept.
Theorem/proposition
Theorem 2.3.3
(A linear-size gate encoding)
For an explicitly encoded Boolean circuit with input variables and gates over constants, binary AND/OR and unary NOT, one can construct in polynomial time a CNF formula with at most three literals per clause and at most variables. It has at most clauses, and for every assignment to the original inputs it has a satisfying extension exactly when the circuit outputs one.
Theorem 2.3.4
(SAT and 3-SAT are NP-complete)
Under the explicit formula encodings and repeated-literal convention above, SAT and 3-SAT are NP-complete. Furthermore every CNF formula can be converted in polynomial time into an equisatisfiable three-CNF formula. Fresh variables are used separately for every gate or clause that needs them.
Proof sketch or proof idea
Name a gate value instead of copying its entire past
Proof
(Gate relations and consistent values)
Give every gate its own output variable . Its source wires are variables already naming input bits or earlier gate outputs. For each type impose the following clauses:
A constant-one gate has unit clause ; a constant-zero gate has unit clause . Add the unit clause naming the designated output wire, requiring it to be one. If the output is directly an input wire, use that input variable in this final clause.
Each gate's clauses express both directions of its relation. For an AND gate, the first two say that forces both inputs to be one; the third says that if both inputs are one, must be one. For an OR gate, the first two force when either input is one, while the third prohibits when both are zero. The NOT clauses force opposite values. These checks prove the relations for all Boolean inputs, not only for a particular successful example.
Given an input assignment, evaluating the circuit supplies one consistent value for every gate. Those values satisfy all defining clauses, and satisfy the final unit clause precisely when the circuit accepts. Conversely, any satisfying assignment to all variables satisfies every gate relation. Induction in topological order forces every gate variable to equal its true evaluated value. The final unit clause then makes the circuit output one. In fact the consistent extension is unique before the output-one requirement is imposed.
There is at most one new variable per gate and at most three clauses per gate, plus the output clause. Each clause has bounded width. Reading the gate list and writing the corresponding fixed patterns takes polynomial time, including the binary indices used as variable names. The transformation retains shared wires by referring repeatedly to their names, rather than repeatedly expanding their expressions.
Concept lensAlgebraic
Gate relations as equations over two elements
Over the three gate relations are the equations for , for , and for . Checking all eight assignments of , and both of , shows that each clause pattern above is satisfied exactly when its equation holds. A circuit then becomes a system of equations of degree at most two, with one equation per gate.
Replace a long disjunction by a chain
Proof
(Chain replacement of a long clause)
For a clause with , introduce distinct fresh variables and replace it with
When the middle conjunction is empty, leaving two clauses. If every original literal is false, the first clause forces , the middle clauses successively force every later , and the final clause is false. Hence satisfying the chain implies that at least one original literal was true.
Conversely, if the original clause is true, assign exactly when all of are false. The first clause holds by this rule. In a middle clause, if its negation already satisfies the clause; if , either the next literal is true or the next prefix remains false and . In the final clause, either its prefix flag is zero or one of the last two literals is true. Thus the chain has a satisfying extension. This proves the per-assignment existential equivalence.
Proof X-ray
What each direction of the chain uses
The linking variable is read as an obligation: the first literals have all failed, so a later literal must still satisfy the clause. The two directions use different things. Soundness, meaning that a satisfied chain gives a true clause, is a forward induction: with every false, the first clause forces , and each middle clause then forces , until the last clause is falsified. Completeness defines by the obligation rule and checks each clause once, splitting on or . The non-obvious point is that the constraints only have to permit consistent obligations, not force a unique one, so several extensions may exist. Freshness of the is the hypothesis spent when several clauses are processed together: a link shared between two clauses can be asked to be and at once, as the third worked example below shows.
A clause of length one or two can be padded by repeating a literal. An empty clause makes the whole input false, so output a fixed unsatisfiable three-CNF, for example . An empty conjunction can instead be sent to a fixed tautological clause. Send malformed input strings to the fixed unsatisfiable formula. A length- long clause uses fresh variables and new clauses. Summing over the explicitly listed occurrences gives a linear number of new symbols apart from the polynomial naming overhead. Freshness across different clauses ensures that their satisfying extensions can be chosen together.
Counterexample mode
The chain is not equal to the clause for every link value
Claim: the chain for , namely , has the same truth value as the clause for every value of . Take and , so the clause is true. With the chain is true, but with the second clause is , so the chain is false. The statement that holds is existential: some value of works. This is why the definition asks for rather than equality.
If three distinct variables are required
The other common convention can also be reached. First delete repeated copies of a literal in a clause. A clause containing both a variable and its negation is a tautology and can be dropped. After this simplification, a clause's different literal occurrences have different underlying variables. The long-clause chain then already has three distinct variables in each new clause, because every link variable is fresh.
For a two-literal clause , introduce a fresh and use . If the original clause is true, both clauses hold for either . If it is false, they demand both values of and are inconsistent. For a unit clause , use two fresh variables and the four clauses , , and . A true satisfies all four; for false , each assignment to falsifies one of the clauses. These are again existential-extension equivalences.
An empty clause can be represented by the conjunction of all eight three-literal sign patterns on three fresh variables. Every assignment falsifies one of those eight clauses, so their conjunction is unsatisfiable. For a true empty conjunction, output one satisfiable three-variable clause. All these replacements use a bounded number of new variables per short clause, preserving the polynomial size bound. Thus the distinct-variable variant is NP-complete as well. Specifying a clause convention makes a proof precise; these gadgets then show why the two conventions have the same complexity classification.
Proof
(NP-completeness from circuit satisfiability)
Finally, the preceding unit proved CIRCUIT-SAT NP-complete. The gate construction, followed by short-clause padding, reduces it to 3-SAT. Since 3-SAT is in NP, it is NP-complete. The same formulas are also ordinary Boolean formulas, so they prove SAT hard, and SAT is in NP. Alternatively, an arbitrary Boolean formula can be regarded as its syntax-tree circuit and encoded by the gate construction. Neither route expands a shared circuit into a potentially enormous tree.
Worked examples
Worked example 2.3.5
(Encode a circuit and recover its internal values)
Let , , and output . The formula contains the three AND clauses, two NOT clauses, three OR clauses and the final unit , for nine clauses. For input , the unique consistent gate values are , so the formula is satisfiable with this input. For , consistency forces , contradicting the output unit. Choosing by hand cannot evade the OR clauses.
Worked example 2.3.6
(A five-literal clause has two link variables)
For , the chain is
If only is true, set . The first clause is satisfied by , the second by , and the last by . If all five are false, the first two clauses force both links to one and the last clause fails. The construction uses three clauses, exactly .
Worked example 2.3.7
(Why different original clauses need different links)
Consider . Fix and , so both original clauses are true. The first four-literal chain forces its link to one, because are false. The second forces its link to zero, because are false. Distinct fresh links allow both requirements. Reusing one link would create a contradiction and incorrectly reject this satisfying original assignment. Freshness is a correctness condition, not merely a naming preference.
Common mistakes
Counterexample mode
One implication per gate is insufficient
If an AND gate is represented only by , then satisfies that clause even though the gate output should be zero. An output assertion could then accept an impossible computation. The full three-clause pattern is needed; saying that the gate output implies “some input is true” is weaker than the AND relation.
Common mistake
(Equisatisfiability does not count assignments)
Equisatisfiability is also different from preserving the number of satisfying assignments. Gate definitions have a unique consistent extension for each original input, but a long-clause chain may have several satisfying link assignments. Ordinary NP-hardness needs preservation of existence. A counting reduction needs an additional multiplicity argument and cannot be claimed merely because the decision reduction works.
Common mistake
(The reduction does not solve the formula)
The transformation does not solve the target formula. It constructs a formula of controlled size whose assignments correspond in the stated existential sense. Enumerating all assignments afterward can still take exponential time; NP-completeness is not a polynomial-time satisfiability algorithm.
Summary
Fresh names preserve circuit sharing; local clauses enforce exact gate relations; a link chain distributes a long clause while preserving existence of an extension. Both directions and the size bound make the reduction complete. With the verifier-to-circuit construction, these arguments prove SAT and 3-SAT NP-complete under the specified encodings.
Exercises
Quick check
(Write the clauses for and verify the case .)
Solution · Answer
The clauses are , and . With both inputs zero, the first two are already true and the last forces . Thus the false-input case is not left unconstrained.
Quick check
(How many fresh variables and clauses does the chain use for an eight-literal clause?)
Solution · Answer
There are fresh variables and clauses. Their conjunction has only eighteen literal occurrences, so the chain's length is linear in the original clause length.
Quick check
(For the four-literal clause , give an assignment to the original variables for which both values of its fresh link are permitted. What does this show about counting assignments?)
Solution · Answer
Set and . Then both and hold for either value of . One original assignment therefore has two extensions. The construction preserves satisfiability but does not automatically preserve its count.
Quick check
(Explain how to handle a CNF input containing an empty clause, and why mapping it to an empty conjunction would be wrong.)
Solution · Answer
An empty clause is false under every assignment, so the entire CNF is unsatisfiable and must map to a fixed unsatisfiable three-CNF. An empty conjunction is true; mapping to it would turn a no-instance into a yes-instance and break the reduction's backward direction.
This completes the circuit-based route introduced in the Trevisan–Williams notes. The explicit clause patterns and boundary conventions here are provided so the satisfiability-preserving statements can be checked directly.