3
$\begingroup$

For circuits with $n$ input bits, we know that, for any function $s$, there are at most $O(s(n)^{s(n)}) = O(2^{s(n) \log s(n)})$ circuits with size at most $s(n)$.

Say two circuits $C_1$ and $C_2$ are different if the function they compute is different, that is, there is an $n$-bit string $x$ such that $C_1(x) \neq C_2(x)$. The $O(s(n)^{s(n)})$ bound above is an upper bound on the number of circuits of a given size. Is there a known lower bound on the number of different circuits with size at most $s(n)$ for different values of $s(n)$ (e.g., $s(n) \in \mathsf{poly}(n)$, $s(n) \in n^{\textsf{polylog}(n)}$, or $s(n) = 2^{n^\varepsilon}$)?

Clearly such a bound must be strictly smaller than the $O(s(n)^{s(n)})$ bound since there are pairs of circuits with different structures (and even different number of gates) and which nevertheless compute the same function (i.e., they are not "different" as defined above)—but how smaller can it be?

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $1000 \leq s \leq 2^n/n$. Every function on $m$ bits can be computed by a circuit of size $O(2^m/m)$ (I believe that even the optimal constant is known). Choose a value of $m$ such that every function on $m$ bits can be computed by a circuit of size $s$, and furthermore $s = \Omega(2^m/m)$. Since there are $2^{2^m} = s^{\Omega(s)}$ different functions on $m$ bits, we see that your upper bound is quite tight.

$\endgroup$
3
  • $\begingroup$ Yes, but this only seem to address the case $s(n) \in O(2^n / n)$ and not other values of $s(n)$. See updated question. $\endgroup$
    – dkaeae
    Commented Mar 10, 2020 at 9:10
  • $\begingroup$ Apply the exact same construction with some $m<n$ to get smaller values of $s$. $\endgroup$ Commented Mar 10, 2020 at 9:11
  • 1
    $\begingroup$ Aha... "the optimal constant is known"—Actually, Lupanov proved we have a $1 + o(1)$ factor (see, e.g., Arora & Barak)... Thanks for the pointer :) $\endgroup$
    – dkaeae
    Commented Mar 10, 2020 at 15:06

Your Answer

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

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