Circuit lower bound

A circuit lower bound proves that every Boolean circuit computing a specified Boolean function requires a certain circuit size, circuit depth or other resource. The gate basis, allowed fan-in and uniformity conditions must be stated. Showing that one construction is large only bounds that construction, not every possible circuit.

For a simple depth bound, consider AND gates, OR gates and NOT gates of fan-in at most two. By induction, a gate at depth $d$ depends on at most $2^d$ input positions. The conjunction of $n$ inputs depends on all $n$, hence requires depth at least $\lceil {\log }_{2}n\rceil$. A balanced tree of AND gates attains the bound. Allowing an unbounded-fan-in AND gate collapses the depth to one, so this proof cannot establish the same bound in that model. General unrestricted polynomial-size lower bounds for explicit hard problems are much more difficult.