Motivation
A polynomial-size circuit family may contain a separate circuit for each input length, with no efficient method for producing the family. Even so, a hypothetical small-circuit algorithm for every NP language would have strong consequences. In particular, it would allow a polynomial-size circuit to find witnesses for all relevant inputs of one length. Guessing such a circuit before a universal challenge turns a two-block universal-existential statement into an existential-universal one.
We prove the Karp–Lipton implication in its standard nonuniform form: if , then the polynomial hierarchy equals its second existential level . The hypothesis is not known to hold, and the conclusion is conditional. The proof does not claim , because a nonuniform circuit family need not be computable from its input length.
We use the quantifier definition of the polynomial hierarchy: in particular, a language in has a polynomial-time predicate and polynomially bounded, fixed-length strings such that
The usual padding conventions let all strings in each block have a specified length. We also use the standard polynomial-size circuit simulation of deterministic polynomial-time computation as background. The witness-search construction and the collapse argument are proved below.
Decision circuits can guide a witness search
Definition 8.3.1
(Witness-prefix language)
Let be a polynomial-time predicate with witnesses of a fixed polynomial length . The prefix language of is
A verifier for guesses the remaining bits of , checks that is a prefix and evaluates . Hence . Under it has polynomial-size decision circuits, although the circuits need not be uniformly constructible.
Theorem 8.3.2
(Nonuniform witness search)
Assume . For every polynomial-time predicate with a fixed polynomial witness-length bound, there is a polynomial-size circuit family such that, whenever a length- input has a valid witness, outputs one valid witness. When no witness exists, the output may be arbitrary.
Proof
(Proof)
For an input length , start with the empty prefix. At each of the positions, ask whether the current prefix followed by zero belongs to for the same input . If yes, append zero; otherwise append one. If a valid witness exists for the current prefix, one of the two extensions has a valid witness, so this choice preserves that invariant. After choices, the prefix is a full valid witness. On inputs with no witness, no correctness claim is needed.
Each query has length bounded by a polynomial in . The relevant query lengths for the stages are determined by and the stage, under a fixed encoding. Select the corresponding polynomial-size nonuniform circuits for , duplicating them as needed. Hardwire the encoding and wire the output of each decision circuit into the next stage's prefix. Unrolling the polynomially many stages gives a circuit of polynomial size: a polynomial number of polynomial-size circuit copies and polynomial-time encoding circuits has polynomial total size. It maps every input of length to a length- string. No algorithm producing this family from is assumed.
Worked example 8.3.3
(Following prefixes of a satisfying assignment)
For the formula , the empty prefix has an extension. Ask whether the prefix has an extension: yes, namely . Fix the first bit to zero. Next ask whether is an extension leading to a satisfying assignment: no, so set the second bit to one. The search returns . The two decisions depend on the same formula, while the second query depends on the first answer. Unrolling records that dependency with circuit wires; it does not enumerate all assignments in the constructed search circuit.
Concept lensCombinatorial
The search as a descent in a binary tree
Arrange all prefixes of length at most as a complete binary tree. Mark a prefix when , that is, when some witness lies below it. The search starts at the root, which is marked exactly when a witness exists, and at each node moves to the child ending in zero if that child is marked, and otherwise to the child ending in one. It therefore follows one marked path to a leaf, and each step costs one membership query to .
Common mistake
(A circuit family is not a uniform search algorithm)
The proof selects the decision circuit for each relevant length from a nonuniform family. It does not provide a polynomial-time machine that, given the length, writes those circuits. On an input without a witness the search circuit can output any string; a later verifier must still check the proposed witness. These qualifications are essential both to the hypothesis and to the soundness argument below.
Counterexample mode
Polynomial-size circuits do not give a decision algorithm
Claim: a language with polynomial-size circuits is decidable, so is no larger than . Take , for a fixed enumeration. For each , a circuit checks that all input bits are and then outputs one fixed constant, the true halting answer for machine . It has size , so . If were decidable, the halting problem would be as well. Hence contains undecidable languages. The repair is to demand uniformity, a polynomial-time algorithm producing the circuit from , which this theorem does not assume.
Why SAT is a sufficient circuit hypothesis
The hypothesis is often stated using SAT alone. This equivalent form depends on the usual NP-completeness of SAT and on simulating a polynomial-time reduction by polynomial-size circuits; we use those standard results as background and show how to handle output lengths.
Proposition 8.3.4
(SAT circuits suffice for NP circuits)
If SAT has polynomial-size nonuniform circuits, then . Conversely, the latter containment implies that SAT has polynomial-size circuits.
Proof
(Proof)
For choose a polynomial-time many-one reduction from to SAT. On inputs of length it produces an encoding of length at most a polynomial . A polynomial-size circuit simulates , outputting both a padded encoding and its actual length . For every possible , select the SAT circuit for inputs of length . Feed the first output bits to that circuit and use the computed length to select its answer. Malformed encodings are rejected according to the fixed SAT encoding. There are only polynomially many possible , and each selected circuit has polynomial size, so the combined circuit has polynomial size in and decides . The selection of the family is nonuniform. The converse is immediate because SAT belongs to NP.
Worked example 8.3.5
(Why output length cannot be silently ignored)
A reduction might output a short formula for one input of length and a longer formula for another input of the same length. A circuit family has a different circuit for each actual length, so it is not enough to choose only the circuit for the maximum length and feed it arbitrarily padded encodings. The selector construction evaluates the correct circuit for each possible length; it does not assume that padding preserves the chosen encoding's meaning.
The same finite-length bookkeeping appears in the witness-search theorem. If every prefix query has length at most and the decision circuits have size at most , then stages use at most decision gates, plus polynomial encoding and wiring overhead. Both and are polynomial, so the resulting bound is polynomial. The circuit is allowed to contain many copies, but it does not contain an exponentially large table of all possible witnesses.
Moving a universal-existential statement to the second existential level
Theorem 8.3.6
(The key Karp–Lipton inclusion)
If , then .
Proof
(Proof)
Let be given by the displayed predicate , and fix an input length . Form using a polynomial-time decodable fixed-length encoding. The witness length is a polynomial in and can be recovered from the encoding. Apply the witness-search theorem to the relation , padding lengths if needed. It gives a polynomial-size circuit which, for every pair of the prescribed lengths that has some valid , outputs one.
For a fixed input , hardwire into that circuit. The resulting polynomial-size circuit takes as input and outputs a candidate . Its description length is bounded by a polynomial in , with one common polynomial bound for all inputs of length . Consider the statement
Checking that is well formed, evaluating it, checking output length and evaluating all take polynomial time in and the description length. Pad the description to a fixed polynomial length and reject invalid encodings. Therefore the statement is in .
If , every has a witness, and the hardwired witness-search circuit works simultaneously for all ; the existential circuit description exists. If , some has no valid witness. For that , no circuit output can satisfy , so no guessed circuit can make the universal check pass. Thus the statement defines exactly .
Proof X-ray
Why guessing a circuit swaps the quantifiers
The statement asks for a witness that may depend on in an arbitrary, possibly exponentially complicated way. The proof turns that dependence into something short enough to guess: a polynomial-size circuit computing from . This is the one non-routine move, and it is exactly where is spent: by the witness-search theorem, the dependence is realized by a small circuit whenever it is realizable at all. After that, the existential choice of comes before the universal , which gives .
Two points keep the proof honest. The circuit is chosen after is fixed, so hardwiring is allowed and needs to work only for this . And the check runs for every , so a wrong guess can never pass: if some has no valid , then fails whatever is. That is why the circuit may output garbage on witness-free inputs without harming soundness. Without the hypothesis there is no reason for such a short description to exist, and the guess could not be bounded polynomially.
Worked example 8.3.7
(What the guessed circuit must accomplish)
Suppose a toy predicate asks, for each two-bit , for a two-bit equal to the bitwise complement of . The circuit succeeds for all four values, so one description passes the universal check. If the predicate is modified so that has no valid response, every proposed circuit fails at that , regardless of how powerful its designer is. This finite example illustrates completeness and soundness of the quantifier transformation; it does not establish the small-circuit hypothesis for NP.
The existentially guessed object is one circuit that must handle every for the given . It is not a separate existential witness chosen after each universal challenge. Conversely, the circuit need not be correct on pairs unrelated to this ; hardwiring is allowed because the outer existential choice is made after the input is known.
Collapsing the remaining levels
Complementation exchanges and . Taking complements of the key inclusion gives , so the two second levels are equal. We now give the induction needed to conclude that every higher level equals them.
Theorem 8.3.8
(Karp–Lipton collapse)
If , then .
Proof
(Proof)
The base equality follows as just explained. Suppose for some that . A statement consists of an outer existential block followed by a predicate. By the induction hypothesis that inner predicate has a description beginning with an existential block. Combine the two adjacent existential blocks into one polynomial-length block. This gives a description, so . The reverse inclusion follows by adding dummy quantifier blocks.
Taking complements yields . Induction proves that all levels at and above two equal the second level. The first levels are contained in it by nesting, so the union of all fixed levels, PH, is .
Worked example 8.3.9
(Combining adjacent existential blocks)
A statement of the form can be written as by encoding the pair as one string . If both original lengths are polynomial in , their combined length is polynomial. This elementary merging is the step used in the induction; exchanging an existential block with a universal one would be a different and generally invalid operation.
Common mistake
(A conditional collapse is not a separation)
The theorem states an implication. It does not establish that is false, because the polynomial hierarchy is not known to be strict. It also does not show that equals P. Small nonuniform circuits, uniform polynomial-time algorithms and hierarchy collapses are related but different claims.
Practice and solutions
Quick check
(Why is the witness-prefix language in NP?)
Say what the certificate is.
Solution · Answer
A witness supplies the remaining bits of . A deterministic verifier checks the length, prefix relation and in polynomial time.
Quick check
(In the search construction, why is one query to the prefix ending in zero enough to select the next bit when an extension is known to exist?)
Consider the two cases for the answer.
Solution · Answer
If the zero extension has a witness, choosing zero preserves the invariant. Otherwise, because the current prefix has at least one full extension, every valid extension must begin with one; choosing one preserves the invariant.
Quick check
(What can the search circuit output when no witness exists?)
Recall what the theorem guarantees.
Solution · Answer
Anything of the specified output length. Correctness is guaranteed only when a valid witness exists, so a verifier must check the result.
Quick check
(In the key inclusion, why can no guessed circuit pass when some universal choice has no valid ?)
Look at the check at that particular .
Solution · Answer
At that particular , every string fails . The circuit's output is one such string, so the universal check rejects regardless of the circuit description.
Quick check
(Why can two adjacent existential blocks be combined without increasing the hierarchy level?)
Think of the pair as one string.
Solution · Answer
Encode the two polynomial-length strings as one polynomial-length string, and let the predicate decode it. The order of the two existential choices does not introduce a new alternation.
Quick check
(Does the Karp–Lipton implication prove ?)
Is the collapse of PH known to be false?
Solution · Answer
No. It says that inclusion would imply a collapse of PH. Without an independent proof that PH does not collapse to its second level, the hypothesis is not ruled out.