Kompleksitas sirkuit adalah studi tentang rangkaian yang dibatasi sumber daya dan fungsi yang dihitung oleh sirkuit tersebut.
Pada 1980-an, Razborov terkenal menunjukkan bahwa ada fungsi Boolean monoton eksplisit (seperti fungsi CLIQUE) yang membutuhkan banyak gerbang AND dan OR secara eksponensial untuk menghitung. Namun, basis {AND, OR} di atas domain Boolean {0,1} hanyalah salah satu contoh dari set gerbang menarik...
Ini adalah pertanyaan tentang kompleksitas rangkaian. (Definisi ada di bawah.) Yao dan Beigel-Tarui menunjukkan bahwa setiap rangkaian keluarga dari ukuran s memiliki keluarga rangkaian yang setara dengan ukuran s p o l y ( log s ) dari kedalaman dua , di mana gerbang keluaran adalah fungsi...
Ryan Williams baru saja memposting batas bawahnya pada ACC , kelas masalah yang memiliki sirkuit kedalaman konstan dengan fan-in dan gerbang tanpa batas DAN, ATAU, BUKAN dan MOD_m untuk semua kemungkinan yang ada. Apa yang istimewa dari gerbang MOD_m? Mereka memungkinkan seseorang untuk...
Biarkan menjadi bilangan bulat positif tetap ukuran bit.AAAnnn Satu diizinkan untuk pra-proses integer ini sebagaimana mestinya. Diberikan bilangan bulat positif dari ukuran bit, apa kompleksitas dari perkalian ?BBBmmmABABAB Catatan kita sudah memiliki algoritma . Pertanyaannya di sini adalah...
Beberapa tahun yang lalu, ada beberapa karya Joel Friedman yang menghubungkan batas bawah dengan kohomologi Grothendieck (lihat makalah: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Apakah garis pemikiran ini membawa wawasan baru ke dalam kompleksitas boolean, atau apakah...
Saya pikir saya akan membagikan pertanyaan ini karena mungkin menarik bagi pengguna lain di sini. Asumsikan bahwa fungsi yang berada dalam kelas yang seragam (seperti ) juga berada dalam kelas kecil yang tidak seragam (seperti A C 0 / p o l y , yaitu tidak seragam A C 0 ), apakah ini menyiratkan...
Biarkan menjadi fungsi Boolean dan mari kita pikirkan f sebagai fungsi dari hingga \ {-1,1 \} . Dalam bahasa ini, ekspansi Fourier dari f hanyalah perluasan dari f dalam hal monomial bebas persegi. ( 2 ^ monomial ini membentuk dasar ruang fungsi nyata pada \ {- 1,1 \} ^ n . Jumlah kuadrat dari...
Dalam bukunya, Boolean Function Complexity, Stasys Jukna menyebutkan (halaman 564) bahwa Kolmogorov percaya bahwa setiap bahasa di P memiliki sirkuit dengan ukuran linier. Tidak ada referensi yang disebutkan dan saya tidak dapat menemukan apa pun secara online. Apakah ada orang yang tahu lebih...
Dalam kompleksitas komputasi ada perbedaan penting antara perhitungan monoton dan umum dan teorema terkenal oleh Razborov menegaskan bahwa 3-SAT dan bahkan PENCOCOKAN tidak polinomial dalam model sirkuit Boolean monoton. Pertanyaan saya sederhana: Apakah ada analog kuantum untuk sirkuit monoton...
Apa kerumitan memutuskan apakah rangkaian dengan bit input dan bit output menghitung permutasi dari ? dengan kata lain, apakah setiap string bit di merupakan output dari rangkaian untuk beberapa input? Sepertinya masalah yang telah dipelajari, tetapi saya tidak dapat menemukan
Permintaan maaf karena mengajukan pertanyaan yang pastinya ada dalam banyak referensi standar. Saya ingin tahu tentang pertanyaan dalam judul, khususnya saya memikirkan sirkuit Boolean, tidak ada kedalaman yang terikat. Saya menempatkan "terkecil" dalam tanda kutip untuk memungkinkan kemungkinan...
Baru-baru ini, Ryan Willams membuktikan bahwa Konstruktivitas dalam Bukti Alami tidak dapat dihindari untuk memperoleh pemisahan kelas kompleksitas: dan T C 0 . NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Constructivity di Bukti Alam adalah suatu kondisi bahwa semua bukti kombinatorial di memenuhi...
Pertanyaan: Berapa ukuran rumus batas bawah paling dikenal untuk fungsi eksplisit di AC 0 ? Apakah ada fungsi eksplisit dengan batas bawah ?Ω(n2)Ω(n2)\Omega(n^2) Latar Belakang: Seperti kebanyakan batas bawah, ukuran rumus batas bawah sulit didapat. Saya tertarik pada rumus ukuran batas bawah...
EDIT (v2): Menambahkan bagian di akhir tentang apa yang saya ketahui tentang masalah. EDIT (v3): Menambahkan diskusi tentang ambang batas di akhir. Pertanyaan Pertanyaan ini terutama merupakan permintaan referensi. Saya tidak tahu banyak tentang masalahnya. Saya ingin tahu apakah ada pekerjaan...
Dalam survei "Sirkuit Kuantum Kedalaman Kecil" oleh D. Bera, F. Green dan S. Homer (hlm. 36 dari ACM SIGACT News, Juni 2007, vol. 38, no. 2) , saya membaca kalimat berikut: Versi klasik (di mana gerbang dan memiliki fanout paling konstan) terbukti lebih lemah dari .Q A
Polinom adalah proyeksi monoton dari polinom g ( y 1 , ... , y m ) jika m = poli ( n ) , dan ada penugasan π : { y 1 , ... , y m } → { x 1 , ... , x n , 0 , 1f( x1, ... , xn)f(x1,…,xn)f(x_1,\ldots,x_n)g( y1, ... , ym)g(y1,…,ym)g(y_1,\ldots,y_m)mmm( n )(n)(n) sedemikian rupa sehingga f ( x 1 , ......
Keadaan pengetahuan kita tentang sirkuit aritmatika umum tampaknya mirip dengan keadaan pengetahuan kita tentang sirkuit Boolean, yaitu kita tidak memiliki batas bawah yang baik. Di sisi lain, kami memiliki batas bawah ukuran eksponensial untuk sirkuit Boolean monoton . Apa yang kita ketahui...
Mengingat jurang baru-baru ini pada kedalaman-3 hasil (yang antara lain menghasilkan kedalaman-3 rangkaian aritmatika untuk penentu atas ), Saya memiliki pertanyaan-pertanyaan berikut: Grigoriev dan Karpinski membuktikan batas bawah untuk rangkaian aritmetika kedalaman-3 yang menghitung matriks...
Apakah ada hipotesis kompleksitas / kripto yang masuk akal yang mengesampingkan kemungkinan bahwa sirkuit ukuran polinomial memiliki ukuran subeksponensial (yaitu dengan ϵ < 1 ) sirkuit batas-kedalaman ( d = O ( 1 ) )?2O ( nϵ)2HAI(nϵ)2^{O(n^\epsilon)}ϵ <
O ( log c n ) O ( n k ) c k n c 2 n kN CNC\mathsf{NC} menangkap gagasan tentang dapat diparalelkan secara efisien, dan salah satu interpretasinya adalah masalah yang dapat dipecahkan dalam waktu menggunakan prosesor paralel untuk beberapa konstanta , . Pertanyaan saya adalah apakah ada kelas...