Podemos contar em profundidade

Podemos calcular uma porta de limiar de bits por circuitos de tamanho polinomial (fan-in ilimitado) de profundidade lg $n$ ? Como alternativa, podemos contar o número de 1s nos bits de entrada usando esses circuitos?$\frac{\lg n}{\lg \lg n}$

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

Note-se que . Portanto, a questão é essencialmente perguntar se podemos salvar um fator lg lg n na profundidade dos circuitos ao calcular portas de limiar.$\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$$\lg \lg n$

Editar:

Como Kristoffer escreveu em sua resposta, podemos salvar um fator . Mas podemos economizar um pouco mais? Podemos substituir O ( lg $\lg \lg n$como(lg$O(\frac{\lg n}{\lg \lg n})$?$o(\frac{\lg n}{\lg \lg n})$

Parece-me que o truque de força bruta em camadas não funciona para economizar até (mais geralmente qualquer função em lg lg n + ω ( 1 ) ).$2 \lg \lg n$$\lg \lg n + \omega(1)$

Considere-se um circuito de Fanin 2 profundidade S ( log n ) . Divida as camadas de C em O ( log n / log log n ) bloqueia cada um dos log log n camadas consecutivas. Agora queremos substituir cada bloco por um circuito de profundidade 2. Ou seja, cada porta na última camada de um bloco depende de no máximo 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$portões da última camada no bloco abaixo. Assim, podemos substituir cada porta na última camada por um DNF de tamanho polinomial, com entradas sendo as portas na última camada do bloco abaixo. Fazer isso para todos os portões nas últimas camadas de todos os blocos e conectá-los deve render o circuito desejado.

Deixe-me observar que este é essencialmente o melhor que se pode obter: o lema da comutação permite limites mais baixos até o profundidade n / log log n .$\log n/ \log\log n$