Ini adalah hasil klasik bahwa setiap rangkaian fan-in 2 AND-OR-NOT yang menghitung PARITY dari variabel input memiliki ukuran minimal dan ini tajam. (Kami mendefinisikan ukuran sebagai jumlah gerbang AND dan OR.) Buktinya adalah dengan eliminasi gerbang dan tampaknya gagal jika kami mengizinkan...
Pertimbangkan alasan berikut: Misalkan menunjukkan kompleksitas Kolmogorov dari string . Teorema ketidaklengkapan Chaitin mengatakan ituxK(x)K(x)K(x)xxx untuk konsisten dan cukup kuat resmi sistem , terdapat konstan (tergantung hanya pada sistem formal dan bahasanya) sehingga untuk setiap...
Pembukaan Sistem bukti interaktif dan protokol Arthur-Merlin diperkenalkan oleh Goldwasser, Micali dan Rackoff dan Babai pada tahun 1985. Pada awalnya, diperkirakan bahwa yang pertama lebih kuat dari yang terakhir, tetapi Goldwasser dan Sipser menunjukkan bahwa mereka memiliki kekuatan yang sama (...
(Von Neumann memberikan algoritma yang mensimulasikan koin yang adil diberikan akses ke koin bias identik. Algoritma ini berpotensi membutuhkan jumlah koin yang tak terbatas (meskipun dalam harapan, cukup banyak saja). Pertanyaan ini menyangkut kasus ketika jumlah lemparan koin yang diizinkan...
Gerbang AND & OR adalah gerbang yang diberi dua input dan mengembalikan AND dan OR mereka. Apakah sirkuit dibuat hanya dari gerbang AND & OR, tanpa fanout, mampu melakukan perhitungan acak? Lebih tepatnya, apakah logspace komputasi waktu polinomial dapat direduksi menjadi sirkuit AND &...
Seperti kita ketahui, fungsi -clique C L I Q U E ( n , k ) mengambil subgraph ( spanning ) G ⊆ K n dari grafik n -vertex lengkap K n , dan menghasilkan 1 iff G berisi k -clique . Variabel dalam hal ini sesuai dengan tepi dari K n . Sudah diketahui (Razborov, Alon-Boppana) bahwa, selama 3 ≤ k ≤ n /...
Ketika dibatasi hingga - input, setiap -circuit menghitung beberapa fungsi . Untuk mendapatkan fungsi boolean , kita bisa menambahkan satu gerbang ambang batas fanin-1 sebagai gerbang keluaran. Pada input , ambang yang dihasilkan - sirkuit kemudian menghasilkan jika , dan menghasilkan jika ; ambang...
Dengan menggunakan algoritma carry look ahead, kita dapat menghitung penambahan menggunakan kedalaman ukuran polinomial 5 (atau 4?) . Apakah mungkin mengurangi kedalaman? Bisakah kita menghitung penambahan dua bilangan biner menggunakan rangkaian keluarga ukuran polinomial dengan kedalaman kurang...
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...
Dua pertanyaan terkait tentang komputasi kedalaman terbatas: 1) Misalkan Anda mulai dengan n bit, dan untuk memulai dengan bit saya bisa 0 atau 1 dengan beberapa probabilitas p (i), secara independen. (Jika itu membuat masalah lebih sederhana, kita dapat mengasumsikan bahwa semua p (i) s adalah...
Dalam makalah "A Compendium of Problem Complete for P" oleh Greenlaw, Hoover dan Ruzzo (PS) (PDF) , ada daftar masalah dalam P yang tidak diketahui berada di NC dan tidak diketahui juga P-complete. . (Daftar ini merangkum semua masalah terbuka dalam survei yang sangat baik oleh Karp dan...
Biarkan menjadi kelas dari semua bahasa reguler.REGREG\mathsf{REG} Diketahui dan \ mathsf {REG} \ tidak \ subset \ mathsf {AC} ^ 0 . Tetapi apakah ada karakterisasi untuk bahasa di \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset
Menurut catatan sejarah (tidak terverifikasi), Kolmogorov berpikir bahwa setiap bahasa dalam PP\mathsf{P} memiliki kompleksitas rangkaian linier. (Lihat sebelumnya pertanyaan dugaan Kolmogorov yang PPP memiliki sirkuit linear-size .) Perhatikan bahwa kandungannya P≠NPP≠NP\mathsf{P}\neq \mathsf{NP}...
Bisakah kita menghitung gerbang ambang bit berdasarkan ukuran polinomial (kipas tidak terbatas) pada kedalaman lg nnnn ? Atau, dapatkah kita menghitung jumlah 1 dalam bit input menggunakan sirkuit ini?lgnlglgnlgnlglgn\frac{\lg n}{\lg \lg n} Apakah ?T C0⊆ A l t T i m e ( O ( lgnlglgn) , O ( lgn...
Adakah referensi yang memberikan perincian tentang batas bawah sirkuit untuk masalah sulit tertentu yang muncul dalam kriptografi seperti bilangan bulat bilangan bulat, masalah logaritma diskrit utama / komposit dan variannya pada kelompok titik kurva eliptik (dan varietas abelian berdimensi...
Paritas dan seperti kembar yang tidak terpisahkan. Atau begitulah tampaknya selama 30 tahun terakhir. Mengingat hasil Ryan, akan ada minat baru di kelas-kelas kecil.AC0AC0AC^0 Furst Saxe Sipser ke Yao ke Hastad semuanya adalah pembatasan paritas dan acak. Razborov / Smolensky adalah perkiraan...
Saya berpikir bahwa teorema hierarki ukuran untuk kompleksitas sirkuit dapat menjadi terobosan besar di bidang ini. Apakah ini pendekatan yang menarik untuk pemisahan kelas? Motivasi untuk pertanyaan itu adalah yang harus kita katakan ada beberapa fungsi yang tidak dapat dihitung dengan ukuran...
Apakah semua fungsi yang Fourier berat terkonsentrasi pada set berukuran kecil (atau istilah dengan tingkat rendah) dihitung dengan
Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational? Saya menduga itu tidak mungkin, dan...
Saya tertarik dengan fungsi Boolean eksplisit f:0,1n→0,1f:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}dengan properti berikut: jika fff konstan pada beberapa subruang affine dari0,1n0,1n\\{0,1\\}^n , maka dimensi dari subruang ini adalaho(n)o(n)o(n) . Tidak sulit untuk menunjukkan bahwa...