Bisakah kita menghitung secara mendalam

Bisakah kita menghitung gerbang ambang bit berdasarkan ukuran polinomial (kipas tidak terbatas) pada kedalaman lg $n$ ? Atau, dapatkah kita menghitung jumlah 1 dalam bit input menggunakan sirkuit ini?$\frac{\lg n}{\lg \lg n}$

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

Perhatikan bahwa . Jadi pertanyaannya adalah dasarnya meminta jika kita dapat menyimpan lg lg n faktor di kedalaman sirkuit ketika menghitung gerbang ambang batas.$\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$$\lg \lg n$

Edit:

Seperti yang ditulis Kristoffer dalam jawabannya, kita dapat menyimpan faktor . Tetapi bisakah kita menabung sedikit lebih banyak? Bisakah kita ganti O ( lg $\lg \lg n$dengano(lg$O(\frac{\lg n}{\lg \lg n})$?$o(\frac{\lg n}{\lg \lg n})$

Tampak bagi saya bahwa trik brute-force berlapis tidak bekerja untuk menyimpan bahkan (lebih umum fungsi apa pun di lg lg n + ω ( 1 ) ).$2 \lg \lg n$$\lg \lg n + \omega(1)$

Pertimbangkan sirkuit fanin 2 depth O ( log n ) . Membagi lapisan C menjadi O ( log n / log log n ) memblokir masing-masing log log n lapisan berturut-turut. Kami sekarang ingin mengganti setiap blok dengan sirkuit kedalaman 2. Yaitu, setiap gerbang di lapisan terakhir dari sebuah blok bergantung pada paling banyak 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$gerbang dari lapisan terakhir di blok di bawah ini. Dengan demikian kita dapat mengganti setiap gerbang di lapisan terakhir dengan DNF ukuran polinomial dengan input menjadi gerbang di lapisan terakhir dari blok di bawah ini. Melakukan ini untuk semua gerbang di lapisan terakhir untuk semua blok dan menghubungkan ini harus menghasilkan rangkaian yang diinginkan.

Biarkan saya perhatikan ini pada dasarnya yang terbaik yang bisa diperoleh: lemma switching memungkinkan untuk batas bawah sampai kedalaman .$\log n/ \log\log n$