Saya tertarik pada sejarah awal hasil yang dipublikasikan tentang pertukaran ruang-waktu untuk tujuan umum. Secara khusus, saya ingin tahu siapa yang pertama kali menggambarkan jenis algoritma berikut untuk mengevaluasi perhitungan yang memiliki grafik aliran data acak dengan derajat O (1)...
Apa kompleksitas komputasi untuk mengoptimalkan berbagai fungsi di atas grup kesatuan ?U( n )U(n)\mathcal{U}(n) Sebuah tugas yang khas, yang timbul sering dalam teori informasi kuantum, akan memaksimalkan kuantitas tipe (atau perintah polinomial lebih tinggi di U ) atas semua kesatuan matriks U ....
Jawab: tidak dikenal. Pertanyaan yang diajukan wajar, terbuka, dan tampaknya sulit; pertanyaannya sekarang adalah wiki komunitas. Gambaran Pertanyaannya adalah mencoba untuk membagi bahasa yang termasuk dalam kelas kompleksitas - bersama dengan mesin Turing keputusan (TMs) yang menerima bahasa...
Apa kompleksitas query yang paling dikenal dari algoritma pembelajaran Goldreich-Levin? Catatan kuliah dari blog Luca Trevisan , Lemma 3, menyatakannya sebagai . Apakah ini yang paling dikenal dalam hal ketergantungan pada n ? Saya akan sangat berterima kasih untuk referensi ke sumber yang dapat...
Saya mencari informasi tentang kompleksitas komputasi perkalian matriks matriks persegi panjang. Wikipedia menyatakan bahwa kompleksitas mengalikan oleh B ∈ R n × p adalah O ( m n p ) (buku sekolah perkalian).A ∈ Rm × nSEBUAH∈Rm×nA \in \mathbb{R}^{m \times n}B ∈ Rn × pB∈Rn×halB \in \mathbb{R}^{n...
Saya memulai PhD saya musim gugur ini dan saya berencana untuk bekerja dalam teori kompleksitas untuk tesis saya. Saya menyusun daftar makalah penting yang harus diketahui oleh setiap ahli teori kompleksitas. Makalah apa yang akan Anda sarankan untuk orang seperti saya? Dan tolong jelaskan secara...
Pertanyaan pertama saya adalah apakah karakterisasi sistem bukti interaktif dikenal untuk semua kelas kompleksitas klasik. Saya akan memanggil P, NP, PSPACE, EXP, NEXP, EXPSPACE, fungsi rekursif dan berulang secara berulang klasik (antara lain). Secara khusus, apakah karakterisasi sistem bukti...
Hasil 1: Teorema Linial-Mansour-Nisan mengatakan bahwa bobot empat fungsi yang dihitung oleh terkonsentrasi pada subset ukuran kecil dengan probabilitas tinggi.AC0SEBUAHC0\mathsf{AC}^0 Hasil 2: The memiliki bobot lebih dari empat, terkonsentrasi pada efisien derajat
Masalah GI dan Knot keduanya merupakan masalah dalam menentukan kesetaraan struktural dari objek matematika. Apakah ada hasil yang membuat koneksi di antara mereka? Koneksi bagus masalah simpul ke fisika statistik telah dieksplorasi melalui simpul polinomial , apakah ada hasil yang serupa untuk ?G...
Apa kelas kompleksitas yang terkait dengan algoritma pencarian lengkap? (jika ada) Apakah NP atau PSPACE? Apakah ada model komputasi terbatas yang menangkap kelas algoritma pencarian lengkap mirip dengan model untuk pemrograman serakah dan
Diberikan sebagai input bilangan bulat dan himpunan dari himpunan elemen , apa kompleksitas menemukan himpunan elemen dari sedemikian sehingga memiliki kardinalitas minimal dan tidak termasuk dalam set ?nnnSSS{1,...,n}{1,...,n}\{1, ..., n\}TTT{1,...,n}{1,...,n}\{1, ...,
Dari komentar di salah satu pertanyaan saya di MathOverflow saya mendapatkan perasaan bahwa pertanyaan mengenai GCD berada di vs P ini mirip dengan pertanyaan mengenai Integer faktorisasi berada di P vs N P .N CNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}N PNP\mathsf{NP} Apakah ada sesuatu seperti...
Untuk waktu yang paling lama saya berpikir bahwa masalah adalah NP-lengkap jika keduanya (1) NP-hard dan (2) ada di NP. Namun, dalam makalah terkenal "Metode ellipsoid dan konsekuensinya dalam optimasi kombinatorial" , para penulis mengklaim bahwa masalah bilangan kromatik fraksi milik NP dan...
Pertanyaan ini ditanyakan oleh Jan Pax di milis Yayasan Matematika . Tentu saja tetapi saya menduga dari jawaban pertanyaan ini bahwa tidak diketahui apakah (jika tidak, akan menjadi satu kemungkinan jawaban untuk pertanyaan itu). Jika tidak diketahui, apakah ada pemisahan
Seperti diketahui semua orang, SAT lengkap untuk kali banyak polynomial . Itu masih lengkap wrt banyak-satu pengurangan.N PNP\mathsf{NP}A C0SEBUAHC0\mathsf{AC^0} Pertanyaan saya adalah berapa kedalaman minimum yang diperlukan untuk reduksi? Lebih formal, Apa yang paling sehingga SAT adalah...
Saya membaca lampiran tentang batas bawah ACC untuk NEXP dalam buku Komputasi Kompleksitas Arora dan Barak . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Salah satu lemmas kunci adalah transformasi dari sirkuit untuk polinomial multilinear atas bilangan bulat dengan gelar...
Saya mencari di internet, tetapi saya tidak dapat menemukan 'daftar besar' varian masalah SAT. Terlepas dari (umum) DUDUK, k-SAT, MAX-kSAT, Setengah SAT, XOR-SAT, NAE-SAT varian apa lagi yang ada? (juga akan sangat berguna jika ada kelas kompleksitas diberikan (jika
Lemma: Dengan asumsi kesetaraan eta kita memilikinya (\x -> ⊥) = ⊥ :: A -> B. Bukti: ⊥ = (\x -> ⊥ x)dengan kesetaraan eta, dan (\x -> ⊥ x) = (\x -> ⊥)dengan pengurangan di bawah lambda. Laporan Haskell 2010, bagian 6.2 menentukan seqfungsi dengan dua persamaan: seq :: a -> b...
Perambatan keyakinan telah terbukti menjadi metode yang sangat kuat melalui penelitian dalam model grafis probabilistik. Namun, saya tidak tahu apa-apa tentang BP yang sebanding dengan metode MCMC di mana kita dapat memiliki skema aproksimasi acak polinomial sepenuhnya (FPRAS) untuk masalah #...
Disebutkan dalam komentar di postingan lain bahwa kelengkapan PSPACE menyiratkan kekerasan APX. Adakah yang bisa menjelaskan / berbagi referensi untuk itu? Apakah ini "ketat"? (yaitu, apakah ada masalah PSPACE-complete yang masalah optimasi mengakui perkiraan faktor konstan dalam waktu...