Circuit complexity

Circuit complexity studies the size and depth of circuits computing finite-input functions.

Languages computable by polynomial-size Boolean circuit families of bounded fan-in and depth $O(\log n)$. One can specify the nonuniform or logspace-uniform convention explicitly. Balanced constant-size operations give examples such as the MOD3 binary divisibility problem without nonuniform advice.

For a binary numeral, its remainder is the sum of its bits weighted alternately by $+1$ and $-1$ from the least significant position. A balanced finite-monoid reduction circuit adds these residues modulo three in two-bit encodings. A final zero test gives a uniform linear-size logarithmic-depth Boolean circuit, proving membership in NC1.

A fixed finite monoid operation has a constant-size Boolean truth-table Boolean circuit on its constant-bit encodings. Reduce $n$ elements in a balanced binary tree to get linear size and logarithmic depth. Associativity ensures that tree grouping does not change the product. MOD3 uses addition in the three-element residue group, with input-position signs handled at the leaves.

A Boolean circuit is a finite directed acyclic graph of Boolean gates with designated inputs and outputs.

The size of a Boolean circuit counts its gates, or in another common convention its wires. The convention must be fixed when stating quantitative bounds. In switching arguments, new clauses created from a decision tree are not separate original gates to be charged in the failure union bound.

Circuit depth is the largest number of counted gates on any input-to-output path in the Boolean circuit. For an AND/OR circuit with negations on input literals, only the AND/OR gates are counted. This convention makes the restriction argument for the Linial-Mansour-Nisan theorem precise.

Given a finite acyclic Boolean circuit and its input assignment, determine the output bit. Topological gate evaluation places the problem in P; it is a standard P-complete problem under logspace many-one reductions. Boolean circuit evaluation is different from Circuit satisfiability problem, which asks whether some assignment succeeds.

The circuit value problem restricted to AND and NOT gates remains P-complete. Replace each OR by $\neg (\neg x\wedge \neg y)$, using a constant-size gadget. Gate indices and gadget positions can be emitted in logarithmic space, and assignments are preserved. Constants, when needed, can be represented by fixed-valued input nodes.

The circuit satisfiability problem asks whether a Boolean circuit has an input on which its designated output is one. It is NP-complete.

A threshold Boolean function outputs one exactly when a weighted sum of its input bits reaches a specified threshold. The unweighted threshold function $f_{n,r}$ tests whether at least $r$ of its $n$ inputs are one.

A majority Boolean function outputs one when more than half its input bits are one. An odd number of inputs avoids a tie convention. For three bits its unique multilinear polynomial is $x_1{x}_2+x_1{x}_3+x_2{x}_3-2x_1{x}_2{x}_3$, so the polynomial method for quantum query lower bounds requires at least two exact queries.

Its $n$ disjoint triples give a product of degree-three multilinear polynomials, with all-variable coefficient $(-2{)}^n$. Hence its degree is $3n$ and its exact quantum query complexity is at least $\lceil 3n/2\rceil$. At the input consisting of repeated $110$ triples, each of the $2n$ one bits is a disjoint sensitive singleton. Thus block sensitivity is at least $2n$, implying a bounded-error quantum query complexity lower bound $\Omega (\sqrt{n})$.

The dual of a Boolean function $f$ is $f^{\ast }(x)=\neg f(\neg x)$. Swapping AND with OR and zero with one in a monotone circuit for $f$ produces a circuit for $f^{\ast }$ by De Morgan's laws.

A circuit family $(C_n)$ contains one circuit for each input length $n$. The circuit for one length may be chosen independently of those for other lengths, so a family is a nonuniform model of computation.

The languages whose length-$n$ indicator functions have Boolean circuits with at most $T(n)$ gates for sufficiently large $n$, over a fixed bounded-fan-in complete basis. The family need not be constructible by one algorithm. Polynomial-size bounds give P/poly; the truth-table upper bound for circuit size applies even to undecidable languages.

OR together one minterm for each accepted length-$n$ input. Each minterm is an AND of the appropriate Boolean literals. There are at most $2^n$ minterms, and their negated input wires can be shared, giving $O(n{2}^n)$ bounded-fan-in gates. This is a nonuniform existence statement, not an algorithm for determining an undecidable truth table.

A circuit family has polynomial size when $C_n$ has at most $n^{O(1)}$ gates.

For any set of lengths $A$, choose at length $n$ a constant-zero Boolean circuit when $n\notin A$, and an AND of all inputs when $n\in A$. This uses $O(n+1)$ gates. If $A$ is undecidable, so is $U_A$, yet it belongs to P/poly. Since all NP languages are decidable by certificate enumeration, this proves P/poly is not equal to NP; it does not resolve containment in the other direction.

$\mathbf{P}/\mathrm{poly}$ is the class of decision problems decided by polynomial-size circuit families.

Constant-depth circuit complexity studies circuit families whose depth is bounded independently of the input length.

The Håstad switching lemma says that a small-width DNF or CNF becomes representable by a shallow decision tree with high probability under a sufficiently sparse random restriction. Iterating it is a central method for proving lower bounds against constant-depth circuits.

Switching-lemma depth reduction applies the Håstad switching lemma to every bottom-layer gate, replaces each restricted gate by a shallow decision tree, and merges adjacent layers of the same gate type. Repetition reduces a constant-depth circuit to a bounded-depth decision tree while retaining many live variables.

Monotone circuit complexity studies Boolean circuits built only from AND and OR gates, without negations. Such circuits compute monotone Boolean functions, but some monotone functions require much larger monotone circuits than unrestricted circuits.

A monotone Boolean circuit uses only AND and OR gates, variables, and optional constants. It computes a monotone Boolean function; negation gates are excluded.

In the finite lattice approximation for monotone clique circuits, set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell =\lfloor {\log }_{2}n\rfloor$. A nonuniversal output accepts at most ${\sum }_{s=2}^{\ell }s!(r-1{)}^s(m/n{)}^s\le 2(\ell rm/n{)}^2$ of uniform positive cliques. Its missing positives require the circuit size times the positive clique error of a truncated lattice meet to be bounded below. A universal output accepts every negative colouring input; those errors require the circuit size times the negative colouring error of a forced-set closure to be at least one. Both alternatives imply the displayed superpolynomial bound by the Razborov gate-by-gate approximation lemma.

The Razborov approximation method replaces the AND and OR operations of a monotone circuit by tractable lattice operations. If each gate introduces only a controlled set of positive or negative errors, a small circuit cannot separate all positive inputs from all negative inputs.

Take upward-closed set families of subsets of $[n]$ of size at most $\ell$, closed under the forcing rule in Razborov closure. Normalize any family containing a set of size at most one to the full family, since its clique predicate is identically true. Intersection is the meet in a lattice; closure of the union is the join in a lattice. A family represents the graphs containing a clique on at least one of its members. The approximate meet can lose positive inputs and the approximate join can acquire negative inputs. The Razborov gate-by-gate approximation lemma charges output errors to those local errors.

Independently colour each vertex with one of $m-1$ colours and join differently coloured vertices. This complete multipartite graph has no $m$-clique. If a forced set $W$ is rainbow but its $r$ witnesses are not, condition on the colours of $W$. The disjoint petals make those failure events conditionally independent. For each witness of size at most $\ell$, the probability of a colour collision is at most $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)/(m-1)$. If this is at most $1/2$, one closure step causes an error with probability at most $2^{-r}$. There are at most $n^{\ell +1}$ possible steps; apply the union bound.

Choose a uniform $m$-subset $Z$ and the graph consisting only of its clique. Acceptance by two approximating set families but rejection by their intersection requires two minimal witnesses whose union has size greater than $\ell$. At least one has size greater than $\ell /2$. The sunflower bound for minimal members of a Razborov-closed family and $\mathbb{P}(W\subseteq Z)\le (m/n{)}^{|W|}$ give $2{\sum }_{s>\ell /2}s!(r-1{)}^s(m/n{)}^s\le 4q^{\ell /2}$.

Fix integers $r$ and $l$. The Razborov closure of a family of vertex sets of size at most $l$ repeatedly adjoins a set $W$ whenever there are $r$ existing sets $W_1,\dots ,W_r$ whose pairwise intersections are contained in $W$. A family equal to its closure is called $r$-closed.

An inclusion-minimal $s$-set in an upward-closed family cannot belong to an $r$-member delta-system of such minimal sets: its proper core would be adjoined by Razborov closure, violating minimality. The Erdős–Rado sunflower lemma therefore bounds the number $a_s$ of minimal $s$-sets. This weaker factorial bound is sufficient for the superpolynomial monotone clique lower bound.

An $r$-closed family has at most $(r-1{)}^k$ inclusion-minimal members of cardinality $k$. This limits the number of cliques accepted by a proper closed approximation.

The Razborov gate-by-gate approximation lemma compares a monotone circuit with the lattice computation obtained by replacing each gate by an approximate meet or join. Every disagreement at the output is charged to an error introduced by one of the circuit's gates.

A natural proof lower bound is based on a property of Boolean functions that is simultaneously constructive, large, and useful against the circuit class being bounded.

A property of $n$-variable Boolean functions is constructive when membership can be decided from a $2^n$-bit truth table in time polynomial in $2^n$.

A property of Boolean functions is large when it contains a nonnegligible fraction, customarily at least $2^{-O(n)}$, of all $n$-variable Boolean functions.

A property is useful against a circuit class when it contains functions at infinitely many input lengths but eventually excludes every function family computed by circuits of the target size in that class.

The Razborov–Rudich natural-proofs barrier says that the existence of sufficiently secure pseudorandom function families rules out constructive, large properties useful against the associated circuit class.

A pseudorandom function family is an efficiently computable keyed family whose oracle behavior cannot be distinguished from that of a uniformly random function by the specified class of resource-bounded algorithms.