Kompleksitas keliling: sirkuit monoton fungsi Mayoritas

8

Seperti yang ditunjukkan dalam makalah "Sirkuit Monoton untuk Fungsi Mayoritas", adalah mungkin untuk membangun sirkuit boolean monoton untuk fungsi mayoritas pada variabel n dengan ukuran O (n ^ 3) dan kedalaman 5,3 log (n) + O (1).

http://link.springer.com/chapter/10.1007/11830924_38

Pertanyaan saya adalah, apa kompleksitas waktu dari konstruksi seperti itu? (Yaitu, waktu yang dibutuhkan untuk membangun sirkuit, diberikan n secara unary)

Alan Carneiro
sumber

Jawaban:

-1

Kompleksitas waktu sering didefinisikan sebagai "jumlah operasi dalam kasus terburuk untuk mesin Turing." Model rangkaian monoton perhitungan bukanlah model waktu Turing. Dengan demikian, tidak berarti untuk mengatakan apa kompleksitas waktu dari rangkaian semacam itu.

Di sisi lain, jika kita melihat model rangkaian monoton sebagai model rangkaian aktual, maka satu "biaya waktu" dari perhitungan adalah kedalaman rangkaian tersebut. Jadi dalam hal itu kompleksitas waktu dari rangkaian yang Anda sebutkan adalah 5.3log (n).

Tentu saja, di sirkuit nyata ada faktor lain selain "kedalaman" yang berkontribusi pada "berapa lama waktu yang dibutuhkan untuk melakukan perhitungan." Sebagai contoh, kawat terpanjang dalam suatu rangkaian sering merupakan hambatan dalam perhitungan VLSI yang sebenarnya karena kapasitansi yang lebih besar membutuhkan waktu lebih lama untuk diisi ulang.

Chris Blake
sumber
6
Pertanyaannya menanyakan kompleksitas waktu "konstruksi". Meskipun tidak jelas, saya menganggapnya sebagai waktu yang dibutuhkan untuk membangun sirkuit, diberikan dan di unary. Ini kedengarannya pertanyaan yang masuk akal bagi saya. Secara khusus, konstruksinya adalah polytime acak, dan menarik untuk ditanyakan apakah dapat dibuat deterministik subeksponensial.
Emil Jeřábek