 Circuit complexity

Circuit complexity measures the resources of Boolean circuits computing a Boolean function. Circuit size counts logic gates or wires under a declared convention; circuit depth measures the longest dependency chain. The allowed logic gates and their fan-in are part of the model.

For the conjunction of $n$ Boolean variables, a chain of two-input AND gates uses $n-1$ logic gates and depth $n-1$. A balanced binary tree still uses $n-1$ logic gates but reduces depth to $\lceil {\log }_{2}n\rceil$. A depth-$d$ Boolean circuit of fan-in at most two can depend on at most $2^d$ inputs, so that depth is optimal for this function. An unbounded-fan-in AND gate would compute it in one layer, showing why the logic gate convention matters.

A circuit family supplies one Boolean circuit per input length. uniform circuit families impose an effective construction rule; an unrestricted nonuniform family can choose separate Boolean circuits independently. Lower bounds therefore need both the Boolean circuit model and the uniformity convention.