# Can Boolean circuits of polylog depth represent all Boolean functions?

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!

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)$$.
• Thanks! So may I conclude that for most functions, the depth $d$ must be $\Omega(n-\log_2 n)=\Omega(n)$? May 17, 2022 at 14:32
• 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. May 17, 2022 at 14:48