Motivation
The earlier reductions began with a problem already known to be hard. That is useful only after one problem has been connected to every language in NP. We now construct that connection. Given a fixed efficient verifier and a particular input, we build a circuit whose remaining input bits are the proposed certificate. The circuit can output one exactly when some certificate convinces the verifier.
The construction must do more than say that a computer is made of logic gates. Its description must have polynomial length, an algorithm must produce it in polynomial time, and every assignment to its input wires must have a specified meaning. We will account for the tape window, the clock, short certificates and halted computations. These details explain why an entire computation can be represented without listing all of its exponentially many possible certificates.
This unit proves NP-completeness of circuit satisfiability. The companion on gate constraints converts the circuit into a small Boolean formula and completes the SAT and 3-SAT conclusions.
Definitions
Definition 2.2.1
(Boolean circuit and CIRCUIT-SAT)
A Boolean circuit is a finite directed acyclic graph with explicitly listed input vertices, constant gates, binary AND/OR gates and unary NOT gates, together with one designated output wire. A gate may supply several later gates. The encoding lists gate types and source indices, so the number of input variables is at most the description length. Malformed descriptions are outside CIRCUIT-SAT. A topological ordering allows evaluation on a given assignment in polynomial time. CIRCUIT-SAT asks whether any assignment makes the designated output one.
Definition 2.2.2
(Normalized certificate format)
Fix a language , a deterministic verifier , and an explicit polynomial bound on certificate length. We can use a verifier with a fixed certificate length depending on . Let
A length- certificate contains a -bit integer , then payload bits. Reject if ; otherwise pass the first payload bits to and ignore the rest. Every original short certificate can be represented, and an accepted new certificate supplies an accepted original one. When , the header and payload are both empty and represent the unique empty certificate.
Call the normalized verifier . Use a deterministic single-tape machine with a fixed finite alphabet, a two-way infinite tape, and head moves left, right or stationary. Its initial tape contains , where is a delimiter and has exactly bits. This is our verifier model for the proof; polynomial simulations between standard machine models are background to its usual machine-independent interpretation. Fix a known polynomial clock bounding every computation of on such inputs, including malformed certificate headers, and enlarge it so , where is the initial nonblank string length.
Make the accept and reject states absorbing: they keep the same state, scanned symbol and head position. Running for exactly steps now has the same answer as halting earlier. No satisfiability assignment is allowed to choose the clock or the machine.
Theorem/proposition
Theorem 2.2.3
(A bounded verifier has a polynomial circuit)
For the fixed normalized verifier and clock above, one can construct from a circuit with input variables such that
The circuit has gates and can be constructed in polynomial time. The hidden constant depends on the fixed machine, not on or .
Theorem 2.2.4
(Circuit satisfiability is NP-complete)
CIRCUIT-SAT belongs to NP, and every language in NP has a deterministic polynomial-time many-one reduction to it. The reduction sends to the circuit , not to a guessed accepting computation.
Proof sketch or proof idea
A finite window is enough
Proof
(Why a finite window suffices)
Write and . At time the head is at distance at most from its starting position zero. Represent tape positions from through , inclusive. This window has cells. It contains the entire initial string and leaves blank buffers on both sides. During the simulated moves the head never reaches its endpoints. Treat an outside neighbor of an endpoint as blank; that convention cannot affect the actual computation represented here.
Let be the tape alphabet and the state set. A cell label is either an ordinary symbol or a marked symbol , meaning that the head is on that cell in state . A legal configuration has exactly one marked cell. The label alphabet is fixed and finite. Encode each label by bits, using a fixed injection. Codes not assigned to labels will be handled by arbitrary default outputs, so each circuit gate computes a total Boolean function.
Why a three-cell neighborhood determines the next cell
Proof
(The three-cell rule as a fixed circuit)
For a legal configuration, the next label at position depends only on positions . If the head is at , its transition writes a symbol and either keeps or removes the marker there. If the head is at and moves right, its new state marks the existing symbol at . A head at moving left acts similarly. If no head enters and the center was not marked, its symbol stays unchanged. A more distant head cannot reach in one move.
Thus there is one fixed function agreeing with the machine on every neighborhood that occurs in a legal configuration. Give the remaining triples any fixed output, such as a blank label. We do not claim that an arbitrary collection of marked cells describes a computation; only legal initial configurations will enter the simulation.
Each output bit of is a Boolean function of bits. It can be built by a truth table: for every input pattern producing one, form the conjunction specifying that pattern, and take the disjunction of those conjunctions. Replace any wide conjunction/disjunction by binary gates. There are at most patterns, a constant because is fixed. Consequently updating one cell needs only constantly many gates. Updating the entire window needs gates.
Concept lensCombinatorial
The computation as a table of cell labels
Write the layers as rows of a table with rows and columns: row lists the cell labels after steps. The three-cell rule says that entry is of the entries . Thus accepts exactly when the table that starts with the initial tape and applies this rule row by row ends with a row containing the accepting label.
Build the layers and read acceptance
Proof
(Layers, induction and acceptance)
The initial layer contains constants for , the delimiter, blanks and the initial head/state. Each payload or header bit is a circuit input. A fixed bit of the code of its tape symbol is either a constant, that input bit or its negation, depending on the codes chosen for symbols zero and one. Hence this layer is explicitly constructible with gates; no arbitrary multi-bit alphabet choice is left to the assignment.
Compose copies of the window-update circuit, connecting each layer to the next. We show by induction on that, for every assignment to the certificate wires, layer encodes the configuration of after steps. Layer is the initial configuration by construction. If layer encodes the true configuration, every cell's neighborhood is legal, so the fixed function returns the true next label and layer encodes the configuration after steps. Hence the last layer is the actual time- configuration. Test, at each cell, whether its label is marked with the accepting state, and OR those tests. There is exactly one head, so the output is one exactly for acceptance. Absorbing halting states ensure that an earlier acceptance is still visible at the final layer.
The total gate count is . To output the description, loop through layer numbers and cell numbers, writing a fixed local gate pattern with source indices pointing to the previous layer. The machine's transition table and local truth table have constant size. Indices need only bits, so the total description has polynomial length and is produced in polynomial time. The reduction has not solved any instance or guessed any certificate while constructing it.
Proof X-ray
What each half of the induction uses
The induction has a base case and a step, and each uses a different hypothesis. The base case uses the free wires only through the bits of : whatever the assignment, the initial layer has exactly one marked cell and a well-formed tape, so legality at time is automatic. The step uses the three-cell rule on legal neighborhoods, which is where the fixed machine and the bounded window matter: the head never reaches an endpoint, and has constant size. What the induction avoids is any claim about arbitrary bit arrays. We never assert that a layer satisfying a few local conditions is globally legal; legality is inherited from the initial layer. The last layer alone suffices for acceptance only because halting states are absorbing, and the size bound is layers times cells, each of constant cost.
It remains to read off both parts of NP-completeness from this construction.
Membership and hardness
Proof
(Membership and hardness)
Finally, CIRCUIT-SAT is in NP: a certificate assigns its explicitly listed input bits, and evaluation verifies the output. For hardness fix any and its verifier. The construction gives
This is the required membership equivalence. The normalization and circuit construction are polynomial, so the reduction is polynomial. A different language may use a different fixed verifier and clock; completeness does not demand a universal constant-size circuit for all languages.
Worked examples
Worked example 2.2.5
(Representing a shorter certificate without changing the problem)
Suppose the original witness bound is . Then and the normalized length is eight. To represent the original witness , take header , followed by payload . The normalized verifier reads length two and passes only to the original verifier. Replacing the last three payload bits changes nothing. Header encodes six and must be rejected, regardless of its payload. Padding does not mean that arbitrary trailing bits are part of the original witness.
Worked example 2.2.6
(A head enters its neighbor's cell)
Suppose a transition is . A neighborhood whose center is marked loses that marker and gets ordinary symbol zero. The cell immediately to its right, if it previously contained ordinary symbol , becomes . Its tape symbol is not overwritten by zero: zero was written at the old head location. For example, the adjacent labels become . This small distinction is what the three-cell rule records.
Worked example 2.2.7
(A clock estimate is a size estimate)
Take a toy input window length and a clock . The chosen positions run from through , giving cell blocks. Twenty update layers require local block updates. If a block update uses a fixed gates, that part of the circuit uses at most gates. This is not a count of possible tapes or witnesses; it counts the explicit operations in one reusable simulation. Growing quadratically grows the size bound while leaving the machine-dependent unchanged.
Common mistakes
Common mistake
(Treating a constant as a free parameter)
The alphabet and state set are constant only because the verifier is fixed before the reduction begins. If the machine description itself were part of the variable input, a size estimate hiding all of it in a constant would be invalid.
Common mistake
(Inferring the clock from the machine description)
Similarly, the clock is a specified polynomial bound supplied by the proof that this verifier works in polynomial time. We are not claiming an algorithm that infers a running-time bound from an arbitrary machine description.
The next claim sounds harmless, and it fails on a concrete machine.
Counterexample mode
Dropping the absorbing convention
Claim: the update function only has to follow the transition table, so a halting state needs no rule. Take a verifier that enters its accepting state after one step, and a clock . At time the marked cell is . The transition table has no entry for this label, so returns the default blank label and the marker disappears. At time no cell carries the accepting state, the final test outputs , and the circuit rejects an input that accepts. The claim is false. Repair: make accept and reject states absorbing, so that maps to itself; the accepting label is then still present at time and the final test outputs .
Common mistake
(Mistaking a circuit for a formula)
The circuit is not yet an ordinary formula. A gate can feed several successors, and duplicating its entire computation each time can cause exponential growth. The next unit introduces auxiliary variables to preserve this sharing while producing a formula. The fact that the simulation has polynomially many gates alone would not justify naively expanding its output into a polynomial-size formula.
Summary
Normalize the certificate length, fix a polynomial clock, encode a legal initial tape, and simulate local updates in layers. The tape window and local alphabet give a polynomial gate count, while explicit indexing gives a polynomial-time constructor. Free input wires represent certificates, so circuit satisfiability captures exactly existential efficient verification.
Exercises
Quick check
(With original witness bound seven, determine the header and total normalized certificate lengths. How is the empty certificate represented?)
Compute first.
Solution · Answer
The header length is and the total is ten. Header specifies the empty original witness; the seven payload bits are ignored. Every three-bit header now describes an allowed length from zero through seven.
Quick check
(Why may invalid cell codes receive arbitrary update values without undermining the reduction?)
Ask which configurations ever occur.
Solution · Answer
Every certificate assignment produces valid initial labels. Induction shows that every subsequent label is an actual machine label, because the local function agrees with the transition rule on legal configurations. The arbitrary cases are never reached. If we allowed arbitrary initial configurations instead, this argument would no longer apply.
Quick check
(Suppose the initial string length is and the clock is . How many represented cells and local updates are used?)
Use .
Solution · Answer
There are cells, and fifteen layers give local updates. The constant gate cost per update and the final acceptance tests must still be included in a full gate count.
Quick check
(Explain why finding one assignment making output zero does not establish .)
Compare the quantifiers in membership.
Solution · Answer
That assignment only shows that one proposed certificate fails. Membership asks whether some assignment is accepted. To prove nonmembership one would need every possible assignment to fail; the reduction does not collapse that universal statement to one failed trial.
The Trevisan–Williams circuit proof provides a complementary reference. Here the finite tape buffers and certificate-length convention have been specified explicitly so the reduction can be followed as an algorithm.