Théorème de la hiérarchie pour la taille du circuit

Je pense qu'un théorème de hiérarchie des tailles pour la complexité des circuits peut être une percée majeure dans le domaine.

Est-ce une approche intéressante de la séparation des classes?

La motivation de la question est que nous devons dire

il existe une fonction qui ne peut pas être calculée par des circuits de taille $f(n)$ et peut être calculée par un circuit de taille où . (et peut-être quelque chose concernant la profondeur)f ( n ) < o ( g ( n ) $g(n)$$f(n)<o(g(n))$

ainsi, si , la propriété ne semble pas naturelle (elle viole la condition de largeur). De toute évidence, nous ne pouvons pas utiliser la diagonalisation, car nous ne sommes pas dans un cadre uniforme.$f(m)g(n) \leq n^{O(1)}$

Y a-t-il un résultat dans cette direction?

En fait, il est possible de montrer que, pour tout suffisamment petit (inférieur à 2 n / n ), il existe des fonctions calculables par des circuits de taille f ( n ) mais pas par des circuits de taille f ( n ) - O ( 1 ) , ou même f ( n ) - 1 , selon le type de portes que vous autorisez.$f$$2^n/n$$f(n)$$f(n)-O(1)$$f(n)-1$

Voici un argument simple qui montre qu'il existe des fonctions calculables en taille mais pas en taille f ( n ) - O ( n ) .$f(n)$$f(n)-O(n)$

Nous savons que:

1. il existe une fonction qui nécessite une complexité de circuit d'au moins 2 n / O ( n ) , et en particulier une complexité de circuit supérieure à f ( n ) .$g$$2^n/O(n)$$f(n)$
2. la fonction telle que z ( x ) = 0 pour chaque entrée x est calculable par un circuit de taille constante.$z$$z(x)=0$$x$
3. si deux fonctions et g 2 ne diffèrent que sur une seule entrée, alors leur complexité de circuit diffère d'au plus O ( n $g_1$$g_2$$O(n)$

Supposons que soit différent de zéro sur N entrées. Appelez ces entrées x 1$g$$N$ . On peut considérer, pour chaque i , la fonction g i ( x ) qui est la fonction indicatrice de l'ensemble { x 1 , … , x i } ; donc g 0 = 0 et g N = g .$x_1,\ldots,x_N$$i$$g_i(x)$$\{ x_1,\ldots,x_i \}$$g_0=0$$g_N=g$

Il y a clairement certains tels que g i + 1 a une complexité de circuit supérieure à$i$$g_{i+1}$ et g i a une complexité de circuit inférieure à f ( n ) . Mais alors g i a une complexité de circuit inférieure à f ( n ) mais supérieure à f ( n ) - O ( n ) .$f(n)$$g_i$$f(n)$$g_{i}$$f(n)$$f(n) - O(n)$

Ce résultat peut être prouvé à l'aide d'un simple argument de comptage. Considérons une fonction aléatoire appliquée aux premiers bits de l'entrée. Cette fonction a presque certainement une complexité de circuit ( 1 + o ( 1 ) ) ( $k$ selon l'argument de comptage de Riordan et Shannon, et correspondant aux bornes supérieures. Ainsi, en choisissant k de sorte que 2 g ( n ) < 2 k / k < f ( n ) / 2 nous pouvons distinguer la taille$(1+o(1))(2^k/k)$$k$$2g(n) < 2^k/k < f(n)/2$ partir de la taille f ( n ) . Notez que les fonctions en question ne seront même pas nécessairement calculables, mais nous pouvons les placer dans la hiérarchie temporelle exponentielle par des techniques standard (tant que nous pouvons calculer la bonne valeur de k ). Nous ne pouvons bien sûr pas prouver une borne supérieure à 2 n / n , car c'est la complexité du circuit du pire cas de toute fonction. $g(n)$$f(n)$$k$$2^n/n$

Les preuves naturelles ne s'appliquent pas à ce type d'argument, car la propriété en question est `` ne pas avoir un petit circuit '', ce qui n'est pas facilement calculable à partir de la table de vérité de la fonction (vraisemblablement). On ne sait pas à quel point les classes de complexité peuvent être réduites à ce type de comptage. Y a-t-il une raison pour laquelle nous ne pouvons pas utiliser un argument de comptage pour prouver les limites inférieures de ? Pas que je sache de. $NE$