Limite inférieure du nombre de circuits (différents) de taille donnée ?

Question

Pour les circuits avec $n$ bits d'entrée, nous savons que, pour toute fonction $s$, il y a tout au plus $O(s(n)^{s(n)}) = O(2^{s(n) \log s(n)})$ circuits de taille maximale $s(n)$.

Dis deux circuits $C_1$ et $C_2$ sont différent si la fonction qu'ils calculent est différente, c'est-à-dire qu'il existe un $n$chaîne de bits $x$ tel que $C_1(x) eq C_2(x)$.Le $O(s(n)^{s(n)})$ lié ci-dessus est un limite supérieure sur le nombre de circuits d'une taille donnée.Y a-t-il un connu borne inférieure sur le nombre de circuits différents avec taille au maximum $s(n)$ pour différentes valeurs de $s(n)$ (par exemple., $s(n) \in \mathsf{poly}(n)$, $s(n) \in n^{ extsf{polylog}(n)}$, ou $s(n) = 2^{n^\varepsilon}$)?

Il est clair qu’une telle limite doit être strictement inférieure à la $O(s(n)^{s(n)})$ lié puisqu'il existe des paires de circuits avec des structures différentes (et même un nombre de portes différent) et qui calculent néanmoins la même fonction (c'est-à-dire qu'ils ne sont pas "différents" comme défini ci-dessus) - mais jusqu'à quel point peut-il être plus petit ?

Answer 1

Laisser 1 000 $ \leq s \leq 2^n/n$.Chaque fonction sur millions de dollars les bits peuvent être calculés par un circuit de taille $O(2^m/m)$ (Je crois que même la constante optimale est connue).Choisissez une valeur de millions de dollars de telle sorte que chaque fonction sur millions de dollars les bits peuvent être calculés par un circuit de taille $s$, et en plus $s = \Oméga(2^m/m)$.Puisqu'il y a $2^{2^m} = s^{\Omega(s)}$ différentes fonctions sur millions de dollars bits, nous voyons que votre limite supérieure est assez serrée.