Le moyen le plus efficace de convertir un circuit en un circuit (de n'importe quelle profondeur) avec fanout de porte 1

EDIT (22 août 2011):

Je simplifie encore la question et je mets à contribution la question. Peut-être que cette question plus simple aura une réponse facile. Je vais également biffer toutes les parties de la question initiale qui ne sont plus pertinentes. (Merci à Stasys Jukna et Ryan O'Donnell d'avoir répondu partiellement à la question d'origine!)

Contexte:

Étant donné un circuit AC ⁰ avec une profondeur k et une taille S, il existe un autre circuit AC ⁰ calculant la même fonction avec une profondeur k et une taille telle sorte que le nouveau circuit a un fanout = 1 pour toutes les portes. En d'autres termes, le circuit ressemble à un arbre (sauf aux entrées, car les entrées peuvent s'étendre à plus d'une porte). Une façon de le faire est de dupliquer toutes les portes qui ont fanout> 1 jusqu'à ce que toutes les portes aient fanout = 1.$O(S^k)$

Mais est - ce la façon la plus efficace pour convertir AC ⁰ circuits AC ⁰ circuits avec sortance 1? J'ai lu ce qui suit dans la leçon 14 des notes de cours de Ryan O'Donnell :

Est-ce à dire qu'il existe un moyen de prendre n'importe quel circuit de profondeur k AC ⁰ de taille S et de le convertir en un circuit AC ⁰ avec fanout 1, profondeur k et taille ? Si oui, comment cela se fait-il et est-ce la méthode la plus connue? $(2kS)^2$

Question d'origine:

Étant donné un circuit AC ⁰ avec une profondeur k et une taille S, quelle est la méthode la plus connue (en termes de minimisation de la taille du circuit du circuit résultant) pour la convertir en un circuit AC ⁰ de profondeur k et de fanout de porte 1? Y a-t-il des limites inférieures connues pour cela?

Question plus récente et plus simple:

Cette question est un relâchement de l'original où je n'insiste pas pour que le circuit résultant soit à profondeur constante. Comme expliqué ci-dessus, il existe un moyen de convertir un circuit AC ⁰ de profondeur k, taille S en un circuit de taille telle sorte que le nouveau circuit ait fanout = 1 pour toutes les portes. Y a-t-il une meilleure construction?$O(S^k)$

Étant donné un circuit AC ⁰ avec une profondeur k et une taille S, quelle est la méthode la plus connue (en termes de minimisation de la taille du circuit du circuit résultant) pour la convertir en un circuit de n'importe quelle profondeur avec le fanout de grille 1?

Je vais essayer de résumer mes commentaires précédents.

Ignorons d'abord le fait que votre circuit d'origine a une profondeur (constante) ; simplement supposer qu'il a une taille S . Soit A le plus petit nombre tel que toutes les tailles de circuit Fanin bornes S peut être transformé en une formule de Fanin bornes F de taille O ( S A ) . Je prétends que le mieux que nous puissions faire à ce jour est d'obtenir A = O ( S / log 2 S ) . Par exemple, on ne sait pas si même si un circuit (Fanin-2) de taille S = O ( n $k$$S$$A$$S$$F$$O(S^A)$$A=O(S/\log^2 S)$$S=O(n)$peut être simulé par une formule de taille inférieure à .$\exp(n/\log n)$

Pour montrer la revendication, on transforme la formule dans un Fanin-2 formule F ' de taille M = O ( S 2 A ) . Il est bien connu que la profondeur D de chaque formule F ' peut être réalisée logarithmique dans sa taille, qui est D = O ( log M ) = O ( A log E ) . [Ce fut la première fois par Khrapchenko 1968, puis la constante sous grand-O a été amélioré pour D ≤ 1,73 log 2$F$$F′$$M=O(S^{2A})$$D$$F′$$D=O(\log M)=O(A\log S)$$D\leq 1.73\log_2M$par plusieurs auteurs.] D'autre part, le résultat le plus connu pour les circuits fanin-2 [Paterson et Valiant, TCS 2 (3), 397-400] dit que . Ainsi, ayant une simulation avec une beaucoup plus petite que S / log 2 S améliorerait le plus connu simulation Taille profondeur pour les circuits.$Depth=O(Size/\log Size)$$A$$S/\log^2 S$

Cependant, ce n'est qu'un "mot d'avertissement" - cela ne répond pas à votre question car vous supposez que votre circuit d'origine a une profondeur constante , ce qui implique que dans ce cas, nous pouvons simplement prendre A = k (ou A = k - 1 si nous avons une seule porte de sortie). La puissance de la simulation Paterson-Valiant est qu'il applique à arbitraire, même des circuits très asymétriques dont la profondeur est presque toute taille! Mais dans votre milieu profondeur limitée, même le cas k = 3 est pas clair: peut chaque circuit profondeur 3 de la taille S être transformée en une formule de taille profondeur 3 beaucoup plus petite que S $k$$A=k$$A=k−1$$k=3$$S$$S^2$? Je suppose que la réponse devrait être «non» (cela pourrait être un exercice intéressant pour les étudiants). Une formule de profondeur 3 n'est qu'un grand OU de CNF. La question est de trouver un OU CNF qui partagent de nombreuses clauses en commun, mais autrement sont « très différents » pour forcer une grande profondeur formule 3.

$S$$D$$3S−2n$$2D$$O(S^2)$$O(D\log S)$

$f$$AC^0$ $k$$S$$f$$D\leq k-1+\lceil\log_2S\rceil$$D\leq k\log S$$\log S$