= 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 <logic gate>[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 <logic gate>[gate] at depth $d$ depends on at most $2^d$ <input> positions. The <logical conjunction>[conjunction] of $n$ <input>[inputs] depends on all $n$, hence requires depth at least $\lceil\log_2n\rceil$. A <balanced binary tree>[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.
Back to article page
