Peut-on compter en profondeur

Peut-on calculer une porte de seuil à bits par des circuits de taille polynomiale (fan-in illimité) de profondeur lg $n$ ? Alternativement, pouvons-nous compter le nombre de 1 dans les bits d'entrée en utilisant ces circuits?$\frac{\lg n}{\lg \lg n}$

Est ?$\mathsf{TC^0} \subseteq \mathsf{AltTime}(O(\frac{\lg n}{\lg \lg n}), O(\lg n))$

Notez que . La question est donc essentiellement de savoir si nous pouvons enregistrer un facteur lg lg n dans la profondeur des circuits lors du calcul des portes de seuil.$\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$$\lg \lg n$

Éditer:

Comme Kristoffer l'a écrit dans sa réponse, nous pouvons économiser un facteur . Mais pouvons-nous économiser un peu plus? Peut-on remplacer O ( lg $\lg \lg n$aveco(lg$O(\frac{\lg n}{\lg \lg n})$?$o(\frac{\lg n}{\lg \lg n})$

Il me semble que l'astuce de force brute en couches ne fonctionne pas pour enregistrer même (plus généralement n'importe quelle fonction dans lg lg n + ω ( 1 ) ).$2 \lg \lg n$$\lg \lg n + \omega(1)$

Considérons un circuit fanin 2 de profondeur O ( log n ) . Divisez les couches de C en blocs O ( log n / log log n ) chacune des couches log log n consécutives. Nous souhaitons maintenant remplacer chaque bloc par un circuit de profondeur 2. A savoir, chaque porte de la dernière couche d'un bloc dépend d'au plus 2 log log n = log $C$$O(\log n)$$C$$O(\log n/\log\log n)$$\log\log n$$2^{\log\log n} = \log n$portes de la dernière couche dans le bloc ci-dessous. On peut ainsi remplacer chaque porte de la dernière couche par un DNF de taille polynomiale dont les entrées sont les portes de la dernière couche du bloc ci-dessous. Faire cela pour toutes les portes dans les dernières couches pour tous les blocs et les connecter devrait donner le circuit souhaité.

Permettez-moi de noter que c'est essentiellement le meilleur que l'on puisse obtenir: le lemme de commutation permet des bornes inférieures jusqu'à la profondeur .$\log n/ \log\log n$