1
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! So may I conclude that for most functions, the depth $d$ must be $\Omega(n-\log_2 n)=\Omega(n)$? $\endgroup$
    – zbh2047
    May 17, 2022 at 14:32
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    May 17, 2022 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.