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.

A Boolean circuit whose current output depends only on its current input, with no stored state or feedback dependency. Its delay is bounded by the longest input-to-output path of logic gates. This differs from a synchronous sequential circuit, whose output can depend on state stored at earlier clock edges.

A combinational logic circuit mapping a binary input code to selected output lines. In a one-of-$k$ register-address decoder, line $i$ is asserted exactly when the address equals $i$, optionally combined with an enable. This selects which processor register may capture a common write-data word.

A transient output error caused by timing differences in a Boolean circuit. A static hazard temporarily changes an output that should remain constant; a dynamic hazard introduces extra transitions when the output should change once. A steady-state truth table cannot detect these timing effects. Consensus theorem terms can remove single-input static hazards in a sum of products, while simultaneous input changes may still produce other hazards.

A transient output error caused by timing differences in a Boolean circuit. A static hazard temporarily changes an output that should remain constant; a dynamic hazard introduces extra transitions when the output should change once. A steady-state truth table cannot detect these timing effects. Consensus theorem terms can remove single-input static hazards in a sum of products, while simultaneous input changes may still produce other hazards.

A logic hazard in which an output intended to remain one briefly falls to zero. In a sum of products, cover every adjacent pair of one-cells in a Karnaugh map with a common product implicant. That term omits the changing input and remains one throughout the transition, holding the OR output high regardless of the other path delays. This argument assumes one input changes at a time and the circuit starts settled.

For a concrete circuit, let $x=\bar{a}\bar{c}$, $y=bc$, $z=\bar{c}d$, $w=y+z$ and $q=x+w$. Give every gate, including each inverter, propagation delay 10 ns. Starting from $a=b=c=d=1$, lower $c$ at time zero. Signal $y$ falls at 10 ns, while $z$ rises only at 20 ns. Their gap passes through the two OR gates, making $q$ fall during 30–40 ns even though its steady-state value remains one.

Adding the two consensus theorem products $\bar{a}b$ and $bd$ preserves the Boolean function and holds the output high across every potentially hazardous single-input transition. The resulting five-term expression factors as $q=bc+(\bar{a}+d)(b+\bar{c})$. When a change of $c$ could leave the output steadily one, $b=1$ and $\bar{a}+d=1$ keep the second product steadily one. In the zero-to-zero case with changing $c$, $b=0$ and $\bar{a}+d=0$ keep both output products zero. Changes of $a,b,d$ use only one polarity each and therefore have no opposite-polarity race. This factored implementation uses three OR gates, two AND gates and two NOT gates, with a 40 ns maximum input-to-output path at the stated delays.

The elapsed time between a change at a logic gate's input and the corresponding settled change at its output, under specified loading and transition conditions. Dependent gate delays add along a path. The combinational critical path gives the longest such input-to-output path; reconvergent paths of unequal delay can produce a logic hazard even when the final Boolean function value does not change.

The combinational critical path is a longest propagation-delay path through a combinational logic circuit. Register-to-register clock timing also includes launch delay, setup time and clock uncertainty. Putting two functional units in series adds their dependent delays; operating them in parallel instead contributes the slower branch plus any subsequent selection delay.

A barrel shifter moves a machine word by a variable number of bit positions through a bounded-depth combinational logic circuit. For a $2^k$-bit machine word, cascade $k$ banks of multiplexers selecting optional shifts of $1,2,\dots ,2^{k-1}$. The binary shift-amount bits select the stages; the chosen distances add. Logical shifts fill vacated positions with zero, whereas bit rotations reconnect the discarded positions. A 32-bit logical barrel shifter can use five banks of 32 two-input multiplexers.

The number of zero bits before the first one, reading a fixed-width binary representation from its most significant bit. The all-zero $n$-bit input has count $n$. Thus ${\mathrm{clz}}_8(00000101)=5$, and ${\mathrm{clz}}_8(00000000)=8$; the width is part of the definition.

For leading-zero count, inspect a word's bytes from most significant to least significant. Every zero byte contributes eight; the first nonzero byte contributes its table value in the title. If all bytes are zero, a word of width $w$ contributes $w$. Defining the zero table entry explicitly makes the all-zero argument a regular case rather than an out-of-range logarithm.

For a block of $2^k$ bits, encode its count leading zeros result as a zero flag $z$ followed by $k$ low count bits $r$. An all-zero block has $(z,r)=(1,0)$; otherwise $z=0$. Two half-block encoders supply flags $z_H,z_L$ and low counts $h,\ell$. Combine them using $z=z_H\wedge z_L$, $r_{k-1}=z_H\wedge \neg z_L$, and $r_i=\mathrm{mux}(z_H,h_i,{\ell }_i)$ for $i<k-1$. A one-bit leaf has $z=\neg x$ and no low count bits. Checking whether the upper half is nonzero, only the lower half is nonzero, or both halves are zero proves the formula.

All count bits are selected in parallel, so $D(n)=D(n/2)+O(1)$ for circuit depth. The circuit size satisfies $S(n)=2S(n/2)+O(\log n)$; summing the work over levels gives $S(n)=O(n)$. Sharing the all-zero flags avoids a serial adder along the critical path.

A Boolean circuit computing the sum of binary representations, possibly including input and output carry bits. Its delay depends on how carries are propagated; specifying an adder does not by itself imply constant circuit depth as the input width grows.

A combinational logic circuit adding two input bits $a,b$ to a sum bit $s=a\oplus b$ and carry bit $c=a\wedge b$. An exclusive or gate and an AND gate implement it. The identity $a+b=(a\oplus b)+2(a\wedge b)$ follows by checking the four input pairs. A half adder has no input carry, so adding three equally weighted bits needs a different circuit or multiple stages.

A selector that routes one of several inputs to its output according to control bits. The displayed two-input version selects $a$ when $s=0$ and $b$ when $s=1$. A word selector applies the same control bit to parallel one-bit multiplexers; its circuit size grows with the word width while its added circuit depth remains constant.

A combinational logic device comparing two fixed-width binary representations. For unsigned inputs $a,b$, a two-output encoding is $L=1$ exactly when $a<b$ and $G=1$ exactly when $a>b$. Equality gives $(L,G)=(0,0)$; $(1,1)$ is unreachable. A one-bit implementation is $L=\neg a\wedge b$, $G=a\wedge \neg b$.

A digital comparator processes one pair of bits per clock cycle, storing a comparison result in a finite-state machine. For least-significant-first unsigned input, a new unequal pair overrides the stored result, while equal bits preserve it: the newest unequal pair has the greatest place value seen so far.

To combine more and less significant digital comparators, compute $E_H=\neg (L_H\vee G_H)$ and use the displayed formulas. Unequal upper blocks decide the order, because their difference outweighs every possible lower-block difference; equal upper blocks delegate the decision to the lower block. This is an associative operation on the three comparison outcomes. A balanced binary tree of these combinations has $O(n)$ circuit size and $O(\log n)$ circuit depth for $n$-bit inputs.

A physical or idealized component implementing a fixed Boolean function on one or more input bits. For example, an AND gate outputs one exactly when both input bits are one. A Boolean circuit connects logic gates; circuit size counts components and circuit depth measures the longest chain of dependencies.

A two-input logic gate whose output is one exactly when its two input bits agree. Its Boolean function is $(a\wedge b)\vee (\neg a\wedge \neg b)$, equivalently $(a\vee \neg b)\wedge (\neg a\vee b)$. This follows by considering the two cases in which inputs are equal. It implements logical equivalence of the input truth values.

The number of load inputs driven by one output of a logic gate. A large fan-out increases the capacitive load and can increase propagation delay; the allowable number also depends on the logic technology and input characteristics.

A logic gate computing $\neg (a\vee b)=\neg a\wedge \neg b$. This is distinct from exclusive or.

A logic gate computing the logical negation of the logical conjunction of its inputs. Thus $\mathrm{NAND}(x_1,\dots ,x_k)=\neg (x_1\wedge \cdots \wedge x_k)$. It implements a logical disjunction of complemented inputs by De Morgan laws.

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.

An arithmetic circuit is a Directed acyclic graph whose input nodes are variables or constants in a field, and whose internal gates perform addition, subtraction, or multiplication. Gates may reuse earlier outputs, so the circuit can represent a polynomial without listing all its monomials.