Can Boolean circuits of polylog depth represent all Boolean functions?

Question

Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to the output. I wonder if Boolean circuits with a depth Polylog in the number of inputs are sufficient to express any Boolean function. I only know that a depth of $O(n)$ is sufficient ($n$ is the number of inputs), by using the disjunctive normal form to construct a Boolean circuit.

Note that this question is different from the $NC$ complexity, since in $NC^i$ the size of the Boolean circuit is also constrained to be polynomial, while this question does not constrain the size. Thank you!

Answer 1

A $k$-ary circuit of depth $d$ has size at most $k^d$, hence polylog-depth circuits of fan-in 2ドル$ have quasipolynomial size. Thus, the vast majority of Boolean functions cannot be computed by such circuits, as most functions require exponential circuit size $\Omega(2^n/n)$.

• zbh2047: Thanks! So may I conclude that for most functions, the depth $d$ must be $\Omega(n-\log_2 n)=\Omega(n)$?
• Emil Jeřábek: Yes. More precisely, since a $k$-ary circuit of depth $d$ even unwinds into a formula of size $k^d,ドル and most Boolean functions require formula size $\Omega(2^n/\log n),ドル it follows that most functions need depth at least $n-\log_2\log n-O(1)$. This bound turns out to be optimal up to an additive constant (but this is nontrivial). See e.g. Wegener, The complexity of Boolean functions.