Boolean Circuits and Nonuniform Complexity: Examples and Counterexamples

Replacing the advice wire by the constant $1$ turns the XOR gate into a NOT gate on $x_1$; the unused input $x_2$ remains an input wire. On $00$, both $M(00,1)$ and $C_2(00)$ output $1$.

Conversely encode $C_2$ by the topological list ``inputs $x_1,x_2$; NOT $x_1$; designate the NOT gate as output.'' A fixed evaluator given this list as advice returns $1$ on $00$ and, for every two-bit $x$, returns $\mathrm{\neg }{x}_1$; the declared input $x_2$ is simply unused.

The same finite instance therefore exhibits both hardwiring and circuit- encoding directions of [L1].

For a fixed $y$, let $F_y(z)={\bigwedge }_{i=1}^m(z_i\leftrightarrow y_i)$. The identity circuit has size $O(m)$ and outputs $C(y)=y$, so $F_y(C(y))=1$ for every $y$.

Hence the predicate has the ${\mathrm{\Sigma }}_2^p$ certificate form $\mathrm{\exists }C\mathrm{\forall }y{F}_y(C(y))=1$. The deterministic check evaluates only the displayed assignment $C(y)$ in $F_y$; it does not try to verify a global claim that $C$ decides satisfiability.

This is the finite local-verification pattern used in the Karp--Lipton argument of [L1].

By [L1], $L$ is undecidable and the chosen $C_n$ computes $L$ on every $n$-bit input. Each $C_n$ is one constant-output gate.

If an algorithm $G$ generated $C_n$ from $1^n$ in polynomial time, then on input $1^n$ we could run $G$, evaluate its output circuit on $1^n$, and answer whether $n\in H$. This would decide the diagonal halting set, contrary to [L1].

Thus the displayed constant-size family is the promised concrete counterexample to uniform generation.