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.

| cite | improve this answer | |
$\endgroup$
  • $\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 at 9:10
  • $\begingroup$ Apply the exact same construction with some $m<n$ to get smaller values of $s$. $\endgroup$ – Yuval Filmus Mar 10 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 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.