Bisakah kita menghitung secara mendalam

19

Bisakah kita menghitung gerbang ambang bit berdasarkan ukuran polinomial (kipas tidak terbatas) pada kedalaman lg nn ? Atau, dapatkah kita menghitung jumlah 1 dalam bit input menggunakan sirkuit ini?lgnlglgn

Apakah ?TC0SEBUAHltTsayame(HAI(lgnlglgn),HAI(lgn))


Perhatikan bahwa . Jadi pertanyaannya adalah dasarnya meminta jika kita dapat menyimpan lg lg n faktor di kedalaman sirkuit ketika menghitung gerbang ambang batas.TC0NC1=SEBUAHL.HaigTsayame=SEBUAHltTsayame(HAI(lgn),HAI(lgn))lglgn


Edit:

Seperti yang ditulis Kristoffer dalam jawabannya, kita dapat menyimpan faktor . Tetapi bisakah kita menabung sedikit lebih banyak? Bisakah kita ganti O ( lg nlglgndengano(lgnHAI(lgnlglgn)?Hai(lgnlglgn)

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

Kaveh
sumber
3
Saya memodifikasi jawaban saya untuk menyertakan suntingan terakhir.
Kristoffer Arnsfelt Hansen

Jawaban:

22

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 nCHAI(catatann)CHAI(catatann/catatancatatann)catatancatatann2catatancatatann=catatanngerbang 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 .catatann/catatancatatann

Kristoffer Arnsfelt Hansen
sumber
1
Terima kasih Kristoffer. Saya menambahkan pertanyaan yang sedikit lebih kuat.
Kaveh
2
Hanya untuk memastikan saya mendapatkan gambaran besar dengan benar: hingga kedalaman sirkuit ini tidak dapat menghitung paritas, pada kedalaman ini mereka tiba-tiba menjadi mampu menghitung N C 1 . lgn/lglgnNC1
Kaveh
2
Itu benar (faktor konstan hingga kedalaman).
Kristoffer Arnsfelt Hansen