Boolean Circuits and Nonuniform Complexity

Fix an input length $n$. Encode a configuration of $M$ by the state, head position, and the $O(p(n))$ tape cells that can be visited in $p(n)$ steps. Each bit of the next configuration depends on only a constant-size neighbourhood of the current configuration, so it is computed by a constant-size Boolean subcircuit. Pad halting configurations so that this update is defined through time $p(n)$.

Wire $p(n)$ copies of the update layer in sequence, initialize the first layer from the $n$ input bits, and read the accepting-state bit in the final layer. There are $O(p(n))$ encoded bits per layer and $p(n)$ layers, so the resulting circuit $C_n$ has $O(p(n{)}^2)$ gates. Replacing its fixed local basis by the page basis changes this bound only by a constant factor.

For every $x\in \{0,1{\}}^n$, $C_n(x)=1$ exactly when $M$ accepts $x$. Thus $(C_n)$ is a polynomial-size family recognizing $L$, as required by [L2]. The construction proves existence of each $C_n$ and does not assert a uniform generator.

Suppose $(C_n)$ has size at most $p(n)$. Encode $C_n$ as a topologically ordered gate list: each of its at most $p(n)$ records contains a constant-size gate tag and at most two indices of $O(\log (n+p(n)))$ bits. This is polynomial advice. A fixed evaluator scans the list in topological order and computes $C_n(x)$ in polynomial time, so [L2] gives an advised decider.

Conversely, let $M(x,a_n)$ run in polynomial time with $\mathrm{\mid }{a}_n\mathrm{\mid }\le p(n)$. Use a fixed self-delimiting encoding $⟨x,a⟩$ whose length depends only on $\mathrm{\mid }x\mathrm{\mid }$ and $\mathrm{\mid }a\mathrm{\mid }$, and let $B=\{⟨x,a⟩:M(x,a)=1\}$. This is a language in $\mathrm{P}$, so [L3] supplies polynomial-size circuits for $B$. For a fixed $n$, put $m_n=\mathrm{\mid }{a}_n\mathrm{\mid }$ and take the circuit for the common encoding length of $⟨x,a_n⟩$ with $\mathrm{\mid }x\mathrm{\mid }=n$. Hardwire the delimiter bits and all bits of $a_n$, leaving only the $n$ bits of $x$ free. Because $m_n\le p(n)$, the resulting $n$-input circuit has polynomial size and agrees with the original computation $M(x,a_n)$; no change to the advice string or its length is made.

Step 1.1 proves the circuit-to-advice inclusion and step 1.2 proves the advice-to-circuit inclusion, including the advice-length and simulation-size bounds.

Let $H=\{n:M_n(n)\text{ halts}\}$ and form the tally language $U=\{1^n:n\in H\}$. A decider for $U$ would decide $H$ by mapping $n$ to $1^n$, so $U$ is undecidable by [L1]. Define the binary length language $L=\{x:1^{\mathrm{\mid }x\mathrm{\mid }}\in U\}$. If $L$ were decidable, its decider restricted to $1^n$ would decide $U$; hence $L$ is undecidable.

For each $n$, choose $C_n$ to be the constant-one circuit if $1^n\in U$, and the constant-zero circuit otherwise. Then for every $x\in \{0,1{\}}^n$, $C_n(x)=1$ exactly when $x\in L$. The circuits have constant size, and their non-effective length-by-length choice is permitted by [L2].

Thus $L$ is both undecidable and recognized by a polynomial-size circuit family.

Let $C_n$ have depth $d=O(\log n)$. Evaluate its output by a depth-first walk. Store the current root-to-gate child-choice word (at most $d$ bits), a constant amount of traversal state per current level encoded in that word, and $O(\log n)$ counters. Whenever a gate address is needed, recompute it from the output by replaying the stored choices, using logspace uniformity to obtain each gate record. This uses $O(\log n)$ space; bounded fan-in lets the walk combine the child values. Thus ${\mathrm{N}\mathrm{C}}^1\subseteq \mathrm{L}$.

Let $M$ be a logspace decider. On inputs of length $n$ it has polynomially many configurations, each indexed with $O(\log n)$ bits, and its start, accepting, and one-step adjacency predicates are logspace uniform. Boolean matrix squaring computes paths of length at most $2^i$ from those predicates. There are $O(\log n)$ squarings, and each Boolean matrix product has bounded-fan-in depth $O(\log n)$ and polynomial size, so start-to-accept reachability has depth $O({\log }^{2}n)$ and polynomial size. The gate indices and wiring are generated in logspace from $(n,i,u,v)$. Hence $\mathrm{L}\subseteq {\mathrm{N}\mathrm{C}}^2$.

The two simulations prove both stated containments without storing a logarithmic stack of logarithmic-size gate addresses.

A topologically numbered gate has at most a fixed number $b$ of type choices and at most two input-wire indices among at most $n+s$ available wires. Thus each gate record has at most $b(n+s{)}^2$ possibilities; choosing an output wire adds at most $n+s$ possibilities.

By [L2], circuits with exactly $r\le s$ gates therefore number at most $(n+s)[b(n+s{)}^2{]}^r$. Summing over $0\le r\le s$ gives at most $(s+1)(n+s)[b(n+s{)}^2{]}^s=2^{O(s\log (n+s))}$ because $s\ge 1$.

Distinct encodings may compute the same function, so this circuit count is also an upper bound on the number of represented Boolean functions.

Put $s=\lfloor 2^n\mathrm{/}(10n)\rfloor$ and let $b$ be the fixed number of available gate types. The explicit encoding in [L1] gives at most $(s+1)(n+s)(b(n+s{)}^2{)}^s$ circuits. Since $b$ is constant, for all sufficiently large $n$ the base-two logarithm is at most $s(2n+O(1))+O(n)<2^n\mathrm{/}3$.

Dividing the resulting bound $2^{2^n\mathrm{/}3}$ by the total $2^{2^n}$ from [L2] gives at most $2^{-2\cdot 2^n\mathrm{/}3}$, which tends to $0$. Hence a uniformly random truth table has size greater than $2^n\mathrm{/}(10n)$ with probability tending to $1$.

This is an existence-and-density argument over truth tables; it does not select or compute an explicit hard family.

A verifier first rejects a malformed list. Otherwise it guesses one bit for every input gate, evaluates the gates in topological order, and accepts iff the designated output is $1$. Its time is polynomial in the list length, so $\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}\mathrm{S}\mathrm{A}\mathrm{T}\in \mathrm{N}\mathrm{P}$.

Given a Boolean formula $\phi$, create one circuit input for each variable and one circuit gate for each connective, ordered from leaves toward the root; designate the root gate as output. This map is polynomial time and produces a circuit $C_{\phi }$ satisfying $C_{\phi }(a)=\phi (a)$ for every assignment $a$. Therefore $\phi \in \mathrm{S}\mathrm{A}\mathrm{T}$ iff $C_{\phi }\in \mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}\mathrm{S}\mathrm{A}\mathrm{T}$, so [L2] and [L3] give NP-hardness.

Combining membership from step 1.1 with hardness from step 1.2 proves NP-completeness by [L4].

Let $R(x,y,z)$ be any polynomial-time predicate with polynomially bounded $z$, and form the NP language $E_R=\{⟨x,y,w⟩:\text{some extension }z⪰w\text{ satisfies }R(x,y,z)\}\mathrm{.}$ By the hypothesis, $E_R$ has polynomial-size decision circuits. Successively querying whether the current prefix has a satisfying extension, first with a $0$ appended and then with a $1$ appended, composes polynomially many copies of these decision circuits into a polynomial-size search circuit. On input $(x,y)$ for which some witness exists, it outputs an actual $z$ satisfying $R(x,y,z)$.

Let $L\in {\mathrm{\Pi }}_2^p$, so $x\in L⟺\mathrm{\forall }y\mathrm{\exists }zR(x,y,z)$. For each fixed input length, step 1.1 supplies a single polynomial-size search circuit $C$ which works for every pair $(x,y)$ of the relevant padded lengths. Therefore $x\in L⟺\mathrm{\exists }C\mathrm{\forall }yR(x,y,C(x,y))\mathrm{.}$ If $x\in L$, choose the search circuit from step 1.1; conversely, any circuit satisfying the right side supplies the required witness for every $y$. The predicate merely evaluates $C$ and checks $R$, so it is polynomial-time and the right side is a ${\mathrm{\Sigma }}_2^p$ formula.

Thus ${\mathrm{\Pi }}_2^p\subseteq {\mathrm{\Sigma }}_2^p$; the reverse containment after complementing gives equality of the second levels. Replacing each inner ${\mathrm{\Pi }}_2^p$ block of a higher alternating formula by its ${\mathrm{\Sigma }}_2^p$ form and merging adjacent existential and universal blocks inductively collapses every constant-alternation level to ${\mathrm{\Sigma }}_2^p$. Consequently $\mathrm{P}\mathrm{H}={\mathrm{\Sigma }}_2^p$.

Let $(C_n)$ be the constant-size family for the undecidable length language from [L2]. If a polynomial-time generator $G$ output $C_n$ on input $1^n$, then on any word $x$ one could compute $G(1^{\mathrm{\mid }x\mathrm{\mid }})$ and evaluate that constant- size circuit on $x$ in polynomial time.

The resulting algorithm would decide the language, contradicting its undecidability. Hence this polynomial-size family has no such generator.

The size condition in [L1] is therefore strictly nonuniform; effective generation is an additional hypothesis.

The argument in [L1] and [L2] compares two cardinalities and concludes that the complement of the set of small-circuit truth tables is nonempty (and large). One can make an ineffective-for-complexity selection computable by enumerating every bounded-size circuit, forming all of their truth tables, and choosing the lexicographically first missing table. That exhaustive procedure, however, takes time exponential (indeed much larger) in the truth-table length and supplies no polynomial-time algorithm for evaluating the selected function on an input.

Consequently the counting proof establishes existential hardness and even permits a brute-force computable choice, but it does not by itself produce an efficiently explicit hard family. Such a family requires an additional efficient construction and lower-bound argument absent from the count.

This distinction refutes the claim that the Shannon counting argument itself supplies a polynomial-time computable hard family.