Ilmu komputer teoretis telah memberikan beberapa contoh "harga abstraksi." Dua yang paling menonjol adalah untuk eliminasi Gaussian dan sortasi. Yaitu: Diketahui bahwa eliminasi Gaussian optimal untuk, katakanlah, menghitung determinan jika Anda membatasi operasi pada baris dan kolom secara...
Ketika merancang suatu algoritma untuk masalah baru, jika saya tidak dapat menemukan algoritma waktu polinomial setelah beberapa saat, saya mungkin mencoba membuktikannya sebagai NP-hard. Jika saya berhasil, saya sudah menjelaskan mengapa saya tidak dapat menemukan algoritma waktu polinomial....
Apa batas bawah terbaik saat ini untuk waktu dan kedalaman rangkaian untuk
Di utas lain , Joe Fitzsimons bertanya tentang "batas bawah terbaik saat ini pada 3SAT." Saya ingin pergi ke arah lain: Apa batas atas terbaik saat ini di 3SAT? Dengan kata lain, apa kompleksitas waktu dari pemecah SAT yang paling efisien? Secara khusus, apakah mungkin untuk menemukan algoritma...
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...
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...
Biarkan PRIMES (alias pengujian awal ) menjadi masalah: Dengan bilangan alami , apakah n bilangan prima?nnnnnn Biarkan FAKTOR menjadi masalah: Dengan bilangan alami , m dengan 1 ≤ m ≤ n , apakah n memiliki faktor d dengan 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1 \leq m \leq...
Keserakahan, karena tidak ada kata yang lebih baik, adalah baik. Salah satu paradigma algoritmik pertama yang diajarkan dalam kursus pengantar algoritma adalah pendekatan serakah . Pendekatan serakah menghasilkan algoritma sederhana dan intuitif untuk banyak masalah dalam P. Lebih menarik lagi,...
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...
Kompleksitas terobosan terobosan baru-baru ini hasil bawah dari Ryan Williams memberikan teknik bukti yang menggunakan hasil batas atas untuk membuktikan kompleksitas batas bawah. Suresh Venkat dalam jawabannya untuk pertanyaan ini, Apakah ada hasil kontra-intuitif dalam ilmu komputer teoretis? ,...
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...
Saya perlu menghitung median berjalan: Input: , k , vektor ( x 1 , x 2 , ... , x n ) .nnnkkk( x1, x2, ... , xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Output: vektor , di mana y i adalah median dari ( x i , x i + 1 , ... , x i + k - 1 ) .( y1, y2, ... , yn - k + 1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc,...
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...
Jelas bahwa setiap masalah yang dapat ditentukan dalam deterministic logspace ( LLL ) berjalan paling banyak waktu polinomial ( PPP ). Ada banyak kelas kompleksitas antara LLL dan PPP . Contohnya termasuk NLNLNL , LogCFLLogCFLLogCFL , NCiNCiNC^i , SACiSACiSAC^i , ACiACiAC^i , SCiSCiSC^i . Hal ini...
Saya tahu bahwa secara sepintas fungsi OR pada variabel dapat direpresentasikan dengan tepat oleh polinomial seperti: , yang bertingkat .x 1 , ... , x n p ( x 1 , ... , x n ) p ( x 1 , ... , x n ) = 1 - ∏ n i = 1 ( 1 - x i ) nnnnx1, ... , xnx1,…,xnx_1,\ldots, x_np ( x1, ... ,...
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 , ......
Selain kompleksitas komunikasi (deterministik) dari suatu relasi , ukuran dasar lain untuk jumlah komunikasi yang dibutuhkan adalah nomor partisi protokol . Hubungan antara kedua ukuran ini diketahui hingga faktor konstan. Monograf oleh Kushilevitz dan Nisan (1997) memberikanRc c ( R )cc(R)cc(R)RRR...
Menyusul dari pertanyaan sebelumnya , apa batas bawah ruang terbaik saat ini untuk SAT? Dengan batas bawah ruang yang saya maksud di sini adalah jumlah sel worktape yang digunakan oleh mesin Turing yang menggunakan alfabet biner worktape. Istilah aditif konstan tidak dapat dihindari karena TM...
Ungkapan tepat dari judul adalah karena Anand Kulkarni (yang mengusulkan situs ini dibuat). Pertanyaan ini diajukan sebagai contoh pertanyaan, tetapi saya sangat ingin tahu. Saya tahu sedikit tentang geometri aljabar, dan pada kenyataannya juga hanya memiliki sepintas, pemahaman sarjana tentang...
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...