Mengikuti saran Josh Grochow, saya mengubah komentar saya dari pertanyaan sebelumnya menjadi pertanyaan baru. Bukti apa yang kita miliki untuk ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Berikut UPUP\mathsf{UP} adalah kelas bahasa dikenali oleh waktu non-deterministik mesin Turing polinomial yang...
Dalam "paragraf terakhir" dari "halaman pertama" dari makalah berikut: Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , "Jika NP Memiliki Sirkuit Ukuran Polinomial, maka MA = AM," Ilmu Komputer Teoretis, 1995. Saya menemukan klaim yang agak kontra-intuitif:
Baru-baru ini, saya menemukan varian pewarnaan tepi berikut. Diberikan grafik tidak terarah yang terhubung, temukan pewarnaan tepi yang menggunakan jumlah warna maksimum dan juga memenuhi kendala bahwa, untuk setiap simpul , insiden tepi untuk paling banyak menggunakan dua warna.vvvvvv Dugaan...
Misalkan saya mempertimbangkan varian BPP berikut, yang kami sebut E (xact) BPP: Suatu bahasa ada di EBPP jika ada waktu polinomial acak TG yang menerima setiap kata dalam bahasa dengan probabilitas 3/4 tepat dan setiap kata tidak dalam bahasa dengan tepat 1/4 probabilitas. Jelas EBPP terkandung...
Apakah NP dalam DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log n})
LogCFL adalah himpunan semua bahasa yang logspace direduksi menjadi bahasa bebas konteks. Demikian pula, LogDCFL adalah himpunan semua bahasa yang logspace direduksi menjadi bahasa bebas konteks deterministik. Lihat artikel wikipedia ini untuk beberapa masalah lengkap LogCFL. Ada beberapa masalah...
Saya bertanya-tanya apakah masalah yang waktu sublinear (dalam ukuran input) algoritma yang ada dapat dicirikan memiliki sifat-sifat tertentu. Ini termasuk waktu sublinear (mis. Pengujian properti, gagasan alternatif perkiraan untuk masalah keputusan), ruang sublinear (mis. Algoritma sketsa /...
Kami mengatakan bahwa NFA adalah Konstanta Ambigu jika ada sehingga setiap kata diterima oleh atau (persis) jalur .MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Jika automaton secara konstan ambigu untuk , maka disebut Unambiguous FA (UFA).MMMk=1k=1k=1MMM Biarkan menjadi bahasa...
Saya butuh daftar bahasa lengkap. Ada dua masalah seperti yang tercantum di Kompleksitas Kebun Binatang , yaitu:Σp2Σ2p\Sigma_2^p DNF setara minimum. Dengan rumus DNF F dan integer k, adakah rumus DNF yang setara dengan F dengan k atau lebih sedikit kemunculan literal? Implan terpendek. Diberikan...
Apa saja contoh pasangan kompleksitas kelas dan sedemikian rupa sehinggaAAABBB kita tidak tahu apakah , danA=BA=BA=B kita tidak tahu relativiasi kontradiktif juga (yaitu, kita tidak tahu orakel dan Q sehingga A P = B P dan A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P = B^PAQ≠BQAQ≠BQA^Q \ne B^Q Untuk...
Saya tertarik jika ada artikel eksposisi yang bagus atau survei yang dapat saya rujuk ketika saya menulis tentang operator kelas kompleksitas : operator yang mengubah kelas kompleksitas dengan melakukan hal-hal seperti menambahkan quantifiers ke dalamnya. Contoh operator Berikut ini dapat...
Diminta oleh pertanyaan yang diajukan Greg Kuperberg kepada saya, saya ingin tahu apakah ada makalah yang mendefinisikan dan mempelajari kompleksitas kelas bahasa yang mengakui berbagai jenis bukti pengetahuan . Kelas-kelas seperti SZK dan NISZK sangat alami dari sudut pandang kompleksitas, bahkan...
Teorema hierarki adalah alat mendasar. Sejumlah besar dari mereka dikumpulkan dalam pertanyaan sebelumnya (lihat Apa hierarki dan / atau teorema hierarki yang Anda ketahui? ). Beberapa pemisahan kelas kompleksitas langsung mengikuti dari teorema hierarki. Contoh pemisahan yang sangat dikenal:...
Kelas kompleksitas BQP sesuai dengan subrutin kuantum waktu polinomial mengambil input klasik dan mengeluarkan output klasik probabilistik. Saran kuantum memodifikasi bahwa untuk memasukkan salinan beberapa status saran kuantum yang telah ditentukan tetapi dengan input klasik seperti biasa. Apa...
Pertanyaan pendek. Apa kekuatan komputasi dari sirkuit "kuantum", jika kita mengizinkan gerbang non-kesatuan (tapi masih tidak dapat dibalik), dan membutuhkan output untuk memberikan jawaban yang benar dengan pasti? Pertanyaan ini dalam arti tentang apa yang terjadi pada kelas EQPEQP\mathsf{EQP}...
Apa beberapa masalah non-sepele di mana kita tahu algoritma saat ini yang kita miliki adalah yang optimal asimptotik? (Untuk mesin turing) Dan bagaimana ini
Kami sering mempertimbangkan kelas kompleksitas di mana kami dibatasi dalam jumlah ruang yang dapat digunakan mesin Turing kami, misalnya: atau . Tampaknya pada awal teori kompleksitas ada banyak keberhasilan dengan kelas-kelas ini seperti teorema ruang-hierarki dan penciptaan pada kelas-kelas...
Ada pekerjaan luar biasa yang dilakukan pada Permanen yang terjadi selama dua dekade terakhir. Saya telah bertanya-tanya untuk sementara waktu tentang kemungkinan algoritma Smooth P untuk Permanen Matriks Nonnegatif. Tentu saja ada algoritma JSV yang terkenal tetapi ini adalah fpras. Berpikir...
Saat membaca makalah " Sebuah teori aplikatif untuk FPH " Anda dapat menemukan bagian berikut: Mempertimbangkan teori yang mengkarakterisasi kelas kompleksitas komputasi, ada tiga pendekatan berbeda: dalam satu, fungsi yang dapat didefinisikan dalam teori adalah "otomatis" dalam kelas...
Masalah P dikatakan dalam APX jika ada beberapa konstanta c> 0 sedemikian sehingga algoritma aproksimasi waktu polinom ada untuk P dengan faktor aproksimasi 1 + c. APX berisi PTAS (terlihat hanya dengan memilih konstanta c> 0) dan P. Apakah APX dalam NP? Secara khusus, apakah keberadaan...