Czy możemy liczyć na głębokość

Możemy obliczyć bramę progową -bitowa przez wielomian wielkości (nieograniczona fan-in) obwody głębokość lg $n$ ? Alternatywnie, czy możemy policzyć liczbę 1s w bitach wejściowych za pomocą tych obwodów?$\frac{\lg n}{\lg \lg n}$

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

Należy zauważyć, że . Pytanie w istocie nasuwa pytanie, czy możemy zapisać współczynnik lg lg n na głębokości obwodów podczas obliczania bram progowych.$\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$$\lg \lg n$

Edytować:

Jak napisał Kristoffer w swojej odpowiedzi, możemy zapisać współczynnik . Ale czy możemy zaoszczędzić trochę więcej? Czy możemy zastąpić O ( lg $\lg \lg n$zo(lg$O(\frac{\lg n}{\lg \lg n})$?$o(\frac{\lg n}{\lg \lg n})$

Wydaje mi się, że warstwowa sztuczka brute-force nie działa na zapisanie nawet (bardziej ogólnie dowolnej funkcji w lg lg n + ω ( 1 ) ).$2 \lg \lg n$$\lg \lg n + \omega(1)$

Rozważmy obwód wentylatora 2 o głębokości O ( log n ) . Podziel warstwy C na O ( log n / log log n ) blokuje każdą log log n kolejnych warstw. Teraz chcemy zastąpić każdy blok obwodem o głębokości 2. Mianowicie, każda bramka w ostatniej warstwie bloku zależy maksymalnie od 2 log dziennika n = log $C$$O(\log n)$$C$$O(\log n/\log\log n)$$\log\log n$$2^{\log\log n} = \log n$bramy ostatniej warstwy w bloku poniżej. Możemy zatem zastąpić każdą bramę w ostatniej warstwie wartością DNF o wielkości wielomianowej, przy czym dane wejściowe są bramkami w ostatniej warstwie bloku poniżej. Wykonanie tego dla wszystkich bramek w ostatnich warstwach dla wszystkich bloków i połączenie ich powinno dać pożądany obwód.

Zauważmy, że jest to w zasadzie najlepsze, co można uzyskać: lemat przełączania pozwala na dolne granice aż do głębokości .$\log n/ \log\log n$