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$
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
    Mar 10 '20 at 9:10
  • $\begingroup$ Apply the exact same construction with some $m<n$ to get smaller values of $s$. $\endgroup$ Mar 10 '20 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
    Mar 10 '20 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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