Motivation
The counting unit introduced nonuniform circuits; the hierarchy unit introduced alternating quantifiers. Here we study what small nonuniform descriptions can express, and a separate conditional collapse of the polynomial hierarchy. These results do not by themselves prove the Karp–Lipton theorem, which connects a circuit hypothesis to a hierarchy collapse and is not proved here.
A second, quantitative result on circuits
A natural question is whether nonuniformity allows every language to have small circuits. It does not, and a short counting argument shows why. We prove a clean version for the number of distinct Boolean functions versus the number of small circuits, using an explicit but crude encoding bound.
Proposition 8.4.1
(Counting small circuits and hard functions)
Fix and an integer . Suppose each circuit over the basis with at most gates (not counting inputs) is described by choosing, for each gate, its type among three and its input sources among the inputs, two constants, and earlier gates, at most candidates. Then the number of distinct functions computed by such circuits is at most . In particular, if , then some function on bits has no circuit with at most gates.
Proof
(Proof)
Order the gates topologically. Each gate is specified by its type (three choices) and by up to two input sources, each chosen from the input variables, the two constants and , and the earlier gates, a set of at most candidates. For the unary gate the second source is simply ignored, so counting two sources for every gate only overcounts. Hence each gate has at most descriptions, and the sequence of gates has at most descriptions. Finally one gate is designated as the output, giving a factor of at most . Each circuit with at most gates (padding smaller circuits with unused gates) has a description in this set, and every function computed by such a circuit is computed by the circuit that a description defines. So the number of computable functions is at most the number of descriptions. There are exactly functions from to . If the number of descriptions is strictly less than , some function is not computed by any such circuit.
To see the condition is satisfiable, take and . Then , , and . So the number of descriptions is at most , using . Meanwhile . Since , some function on bits requires more than gates in this basis. The argument is non-constructive: it proves existence of hard functions without exhibiting any.
The same estimate yields a whole language outside , not just one hard ten-bit function. For sufficiently large , take . The logarithm of the circuit-description bound is , which is smaller than eventually. Choose the lexicographically first truth table absent from those descriptions at each such length, and choose arbitrary functions at the finitely many smaller lengths. Together these truth tables define a language. Since eventually exceeds every polynomial in , no polynomial-size circuit family can compute this language. Finding the first missing table by enumeration can be extremely expensive; this argument gives no polynomial-time decider for the language.
Concept lensCombinatorial
Circuits as short descriptions
By the proof, a circuit with at most gates is written down by at most bits, while a truth table on inputs has bits. The proposition says the same thing as a pigeonhole fact: there are fewer short descriptions than truth tables, so some truth table has no short description. At , the descriptions number fewer than against tables.
Advice and polynomial-size circuit families
A family of circuits allows a different finite object for every input length. An advice machine expresses the same freedom in another language: a single polynomial-time algorithm receives a length-dependent string that need not be computable from that length. The string is fixed for all inputs of a given length. It may not depend on the particular input, and the single algorithm must work for every length.
Definition 8.4.2
(Polynomial advice)
A language is in in the advice sense if there are a deterministic polynomial-time machine , a polynomial , and strings of length at most such that, for every of length ,
The machine has no obligation to produce . The notation does not assert that the advice solves a different problem for each input; its same serves all strings of length .
Theorem 8.4.3
(Advice and circuits characterize the same class)
A language has polynomial-length advice for a deterministic polynomial-time machine exactly when it has a family of polynomial-size Boolean circuits, one circuit for each input length.
Proof
(Proof)
First suppose circuits have at most gates for a polynomial . Put a finite description of in . A gate record specifies its type and, in topological order, the indices of its input sources. Each index uses bits, so the complete description has polynomial length. On input , one fixed deterministic machine reads the description and evaluates the gates in order, retaining their Boolean values. This takes polynomial time and produces . The advice need not be efficiently constructible: existence of the descriptions suffices.
Conversely, suppose and satisfy the advice definition and run in time at most , where is polynomial after including the advice length. A time- computation visits only polynomially many tape cells. Encode its entire bounded configuration by polynomially many bits, including tape symbols, head markers and state. For a fixed machine, the contents of each cell and its head marker in the next configuration are determined by a constant-size local neighborhood and the finite transition table. A polynomial-size Boolean circuit therefore transforms the encoding of one configuration into the next. Compose copies, padding a halting computation with unchanged configurations. The initial encoding is formed from the input variables and the fixed bits of ; constants hardwire those advice bits into the circuit. The output gate reads the final accept bit. Its size is polynomial in and it decides on all inputs of length . For small lengths choose the finitely many circuits separately. No algorithm producing the sequence was assumed, so the resulting family need not be uniform.
The construction proves equivalence of two nonuniform definitions. It does not prove : if the advice were always computable efficiently, it could be generated inside , but arbitrary advice is allowed. Conversely, merely knowing that each individual input has a short helpful string would give the string access to the input and would not be this definition.
Counterexample mode
Polynomial advice does not make a language decidable
It is tempting to argue that a language with polynomial advice is decidable, since each advice string is a finite object and is an ordinary algorithm. The claim is false. Fix an enumeration of Turing machines and let . Take the one-bit advice if halts and otherwise, and let accept exactly when is a nonempty string of ones and . Then runs in linear time, , and exactly when , so . Yet a decider for would decide whether a given machine halts on the empty input. Each exists, but the definition never asks for an algorithm that finds it. The repair is the extra hypothesis that can be computed from in polynomial time, which does give a language in ; see the practice questions.
Worked example 8.4.4
(A circuit encoded once for each length)
For length , let compute using a fixed constant-size AND, OR and NOT implementation of each XOR. Its advice can be a list of gate types and source indices. The evaluator receives this same list on all eight inputs of length three, changing only the input bits. For , the circuit description can be a different list. The existence of a list for every length is what matters; this example happens to have an easy uniform pattern as well.
Worked example 8.4.5
(Advice is shared, not an answer for each input)
Suppose contains exactly those two-bit strings whose first bit is . At length two the one-gate circuit gives the right answers for all four strings. An alleged advice rule that assigns the single bit to the input and to the input has instead chosen advice after seeing the input. That is not a legal advice sequence , even though each individual answer is only one bit long.
Worked example 8.4.6
(A nonconstructive hard function at a length)
At , the preceding circuit-count bound gives fewer than descriptions for circuits with at most gates, while there are Boolean functions. Some truth table is therefore missing from the list. This does not identify a particular hard function, and a lower bound at this one length alone does not rule out a polynomial-size family for a language: asymptotic circuit complexity concerns all sufficiently large lengths and a common polynomial bound.
The two arguments in this unit answer different questions. The circuit count shows that some language has no polynomial-size circuit family; the conditional collapse concerns all languages at each hierarchy level under an equality hypothesis about uniform classes. Neither conclusion follows merely from the other. To apply the collapse proof, keep its assumption visible throughout the induction: the assumption supplies the conversion from a universal block to an NP verifier. The later Karp–Lipton theorem has a different hypothesis and requires additional arguments not developed here.
Collapses
If a level satisfies , the polynomial hierarchy collapses to that level; this standard theorem is stated without proof here. Similarly, quantified Boolean formula is PSPACE-complete when the number of alternating quantifier blocks is not fixed in advance; that result requires a separate proof. Neither statement asserts a known strict separation between hierarchy levels.
Although the general collapse theorem is not proved here, its first case has a short, complete proof that shows the mechanism. The key observation is that removing the outermost quantifier block from a statement leaves a statement about a pair.
Proposition 8.4.7
(A collapse from the first level)
If , then for every , so . In particular, if , then .
Proof
(Proof)
Assume . We prove by induction on that . The case is the definition. Suppose . By the complement proposition in the hierarchy unit, , and by hypothesis this equals .
Let , with outer block of length followed by alternating blocks beginning with a universal one, and predicate . Define
Use a standard pair encoding from which can be recovered in polynomial time and whose length is at least . The quantified lengths are polynomially bounded in that pair length, so this is described by alternating blocks starting universally, with a polynomial-time predicate. Thus . Let be a verifier for using certificates of length at most . Then
where , which is bounded by a polynomial in because the pair encoding has length polynomial in . The pair is a certificate of polynomial length checked in polynomial time, so . Therefore , and the reverse inclusion is nesting. This completes the induction. Then as well, so every level equals .
If , then , because is closed under complement. The hypothesis of the first part holds, so .
Proof X-ray
Where the hypothesis is spent
The induction hypothesis enters only through the complement: it gives . The assumption is then spent exactly once, to read as . This is the non-obvious move: a language whose membership is a universal statement acquires an existential certificate . Once it has one, the outer and the new are adjacent existential quantifiers and merge into a single block, so blocks have become one.
Two details keep the argument honest. The pair has length polynomial in because ; otherwise the certificate bound would not translate into a polynomial in . And without the induction hypothesis only gives , which offers no short certificate of membership, so the universal block could not be removed.
The same induction, with replaced by throughout, is the standard route to the general statement, but that route needs additional bookkeeping that we do not carry out here. The proof above also shows why nothing is known to force a collapse unconditionally: it used the hypothesis exactly to turn a universal statement into an existential one, and no such conversion is known to be available for a general predicate.
Common mistake
(A collapse to NP is not a collapse to P)
The proposition assumes and concludes . It does not conclude : the equality is not known to imply . Only the stronger hypothesis gives .
Practice and solutions
Quick check
(If an advice machine uses for inputs of length , may it replace by a different string for each input of that length?)
Ask what the advice is allowed to depend on.
Solution · Answer
No. The advice is fixed by the length, so it is the same for every input of that length. The algorithm may of course inspect the input while processing that fixed advice.
Quick check
(If an advice sequence can itself be computed from in deterministic polynomial time, show that its language is in .)
Let the machine generate the advice itself.
Solution · Answer
On input , compute , generate from , and simulate the advice machine on . Both phases take polynomial time, so their composition is polynomial.
Quick check
(Does the existence of a function on ten bits requiring more than fifty gates prove that an explicitly named language lies outside ?)
Ask whether the counting argument names the missing function, and for how many lengths it speaks.
Solution · Answer
No. The counting proof does not identify the missing truth table; moreover it concerns a single length and a fixed gate bound. Exclusion from requires ruling out every polynomial size bound across the whole family.