Buka masalah di perbatasan TCS

Di utas Masalah utama yang belum terpecahkan dalam ilmu komputer teoritis? , Iddo Tzameret membuat komentar luar biasa berikut:

Saya pikir kita harus membedakan antara masalah terbuka utama yang dipandang sebagai masalah mendasar, seperti , dan masalah terbuka utama yang akan menjadi terobosan teknis, jika dipecahkan, tetapi tidak harus sebagai hal mendasar, misalnya, batas bawah eksponensial pada sirkuit (yaitu, AC ^ 0 + \ mod 6 gerbang). Jadi kita mungkin harus membuka wiki komunitas baru yang berjudul "masalah terbuka di perbatasan TCS", atau sejenisnya.$P\neq NP$$AC^0(6)$$AC^0+\mod 6$

Karena Iddo tidak memulai utas, saya pikir saya akan memulai utas ini.

Seringkali masalah terbuka utama bidang diketahui para peneliti yang bekerja di bidang terkait, tetapi titik di mana penelitian saat ini macet tidak diketahui oleh orang luar. Contoh yang dikutip adalah yang baik. Sebagai orang luar, jelas bahwa salah satu masalah terbesar dalam kompleksitas sirkuit adalah untuk menunjukkan bahwa NP membutuhkan sirkuit ukuran super-polinomial. Tetapi orang luar mungkin tidak menyadari bahwa titik saat ini di mana kita terjebak sedang mencoba untuk membuktikan batas bawah eksponensial untuk sirkuit AC ⁰ dengan gerbang mod 6. (Tentu saja mungkin ada masalah kompleksitas rangkaian lainnya yang memiliki kesulitan serupa yang akan menggambarkan di mana kami macet. Ini tidak unik.) Contoh lain adalah menunjukkan batas waktu ruang yang lebih rendah untuk SAT lebih baik daripada n ^1,801 .

Utas ini untuk contoh seperti ini. Karena sulit untuk mengkarakterisasi masalah seperti itu, saya hanya akan memberikan beberapa contoh properti yang memiliki masalah seperti:

1. Sering tidak akan menjadi masalah besar terbuka di lapangan, tetapi akan menjadi terobosan besar jika diselesaikan.
2. Biasanya tidak terlalu sulit, dalam arti bahwa jika seseorang mengatakan kepada Anda bahwa masalahnya telah diselesaikan kemarin, ini tidak akan terlalu sulit untuk dipercaya.
3. Masalah-masalah ini juga akan sering memiliki angka atau konstanta yang tidak mendasar, tetapi mereka muncul karena ini adalah tempat kita terjebak.
4. Masalah di perbatasan bidang tertentu akan terus berubah dari waktu ke waktu, berbeda dengan masalah terbesar di bidang itu, yang akan tetap sama selama bertahun-tahun.
5. Seringkali masalah ini adalah masalah termudah yang masih terbuka. Misalnya kita tidak memiliki batas bawah eksponensial untuk AC ¹ , tetapi karena [6] termasuk dalam kelas itu, secara formal lebih mudah untuk menunjukkan batas bawah untuk [6], dan dengan demikian pada batas arus kompleksitas sirkuit.$AC^0$$AC^0$

Silakan kirim satu contoh per jawaban; standar daftar besar dan konvensi CW berlaku. Jika seseorang dapat menjelaskan jenis masalah apa yang kami cari lebih baik daripada yang saya miliki, silakan mengedit posting ini dan membuat perubahan yang sesuai.

EDIT: Kaveh menyarankan bahwa jawaban juga mencakup penjelasan mengapa masalah yang diberikan ada di perbatasan. Sebagai contoh, mengapa kita mencari batas bawah terhadap AC ⁰ [6] dan bukan AC ⁰ [3]? Jawabannya adalah kita memiliki batas yang lebih rendah terhadap AC ⁰ [3]. Tetapi kemudian pertanyaan yang jelas adalah mengapa metode tersebut gagal untuk AC ⁰ [6]. Akan lebih baik jika jawaban dapat menjelaskan hal ini juga.

Berikut adalah tiga penelitian jalur terpendek:

O ( n + m log w ) 2 $1$ . Apakah ada algoritma waktu linier untuk jalur terpendek sumber tunggal dalam grafik langsung dengan bobot non-negatif, setidaknya dalam model komputasi kata-RAM? Perhatikan bahwa ada algoritma waktu linier untuk grafik yang tidak diarahkan (lihat makalah Thorup). Berdasarkan itu, Hagerup memiliki runtime untuk grafik berarah dengan bobot dibatasi . Apakah ada algoritma yang lebih cepat?$O(n+m\log w)$$2^w$

O ( n ω n ) ω < 2.376 O ( n 2.575 ) O ( n ω n $2$ . Apakah ada algoritme polylog untuk semua pasangan jalur terpendek dalam grafik berarah tertimbang? ( adalah eksponen dari perkalian matriks). runtime terbaik saat ini adalah oleh Zwick, dan untuk grafik tidak berarah masalah dapat diselesaikan dalam polylog .$O(n^\omega$$n)$$\omega<2.376$$O(n^{2.575})$$O(n^\omega$$n)$

(Apakah masalah yang diarahkan sebenarnya lebih sulit?)

O ( n 2.9 ) n 0 , … , $3$ . Apakah ada algoritma untuk semua pasangan jalur terpendek dalam grafik -node dengan bobot dalam { }? Atau, apakah ada pengurangan dari masalah umum semua pasangan jalur terpendek ke pembatasan ini?$O(n^{2.9})$$n$$0,\ldots,n$

Ini sudah disebutkan dalam pertanyaan:

Buka:

Pisahkan dari ( sirkuit dengan kedalaman 2). A C 0 2 [ 6 ] A C 0 [ 6 $EXP^{NP}$$AC^0_2[6]$$AC^0[6]$(lihat pembaruan di bawah)

[November 11, 2010] Pisahkan dari . Pisahkan dari .A C 0 2 [ 6 ] E X P N P T C $EXP$$AC^0_2[6]$$EXP^{NP}$$TC^0$

Dikenal:

1. [Alexander Razborov 1987 - Roman Smolensky 1987] tidak ada dalam jika adalah bilangan prima dan bukan kekuatan . A C 0 [ p k ] p m $MOD_m$$AC^0[p^k]$$p$$m$$p$

2. [Arkadev Chattopadhyay dan Avi Wigderson 2009] Biarkan m, q menjadi bilangan bulat co-prime sehingga m bebas persegi dan paling banyak memiliki dua faktor utama. Misalkan C adalah sirkuit tipe mana adalah gerbang atau dan gerbang di pangkalan memiliki set penerimaan yang berubah-ubah. Jika C menghitung maka fan-in teratas, dan karenanya ukuran sirkuit, harus . G A N D O R M O D m M O D q 2 Ω ( n $MAJoGoMOD^A_m$$G$$AND$$OR$$MOD_m$$MOD_q$$2^{{\Omega(n)}}$

Hasil selanjutnya didasarkan pada memperoleh batas korelasi kecil dari fungsi secara eksponensial dengan - kedalaman-2 dan memperkirakan jumlah eksponensial yang melibatkan polinomial derajat rendah.$MOD_q$

Hambatan:?

Perbarui [Nov. 10, 2010]

Sebuah makalah oleh Ryan Williams tampaknya telah menyelesaikan masalah terbuka ini menggunakan metode yang pada dasarnya berbeda dari yang disebutkan di atas:

[Ryan Williams 2010] tidak memiliki sirkuit tidak seragam dengan ukuran . A C C 0 2 n o ( 1 $E^{NP}$$ACC^0$$2^{n^{o(1)}}$

Referensi:

• AA Razborov. Batas bawah pada ukuran jaringan kedalaman terbatas atas dasar yang lengkap dengan penambahan logis (Rusia), dalam Matematicheskie Zametki, 41 (4): 598-607, 1987. Terjemahan Bahasa Inggris dalam Catatan Matematika dari Akademi Ilmu Pengetahuan USSR, 41 (4): 333–338, 1987.

• R. Smolensky. Metode aljabar dalam teori batas bawah untuk kompleksitas sirkuit Boolean. Di STOC, halaman 77–82. ACM, 1987.

• Arkadev Chattopadhyay dan Avi Wigderson. Sistem Linier dibandingkan Moduli Komposit , FOCS 2009

• Ryan Williams. Sirkuit ACC Sirkuit Non-Seragam Batas Bawah , 2010, konsep (diserahkan?)

Biarkan CNF-SAT menjadi masalah dalam menentukan apakah formula CNF yang diberikan memuaskan (tidak ada batasan lebar klausa).

Apakah CNF-SAT pada variabel dan klausa dapat diselesaikan dalam waktu , untuk beberapa ?m 2 δ n p o l y ( m ) δ < $n$$m$$2^{\delta n} poly(m)$$\delta < 1$

Ini adalah masalah terbuka yang terkenal di bidang "algoritma lebih cepat untuk NP". Saya tidak berpikir itu telah mencapai status "masalah terbuka utama" tetapi telah menarik sedikit perhatian. Algoritma yang paling dikenal dijalankan dalam waktu (mis., Di sini ).$2^{n-\Omega(n/\log (m/n))}$

Terkait dengan Hipotesis Waktu Eksponensial (bahwa 3SAT tidak dalam waktu subeksponensial), ada juga "Hipotesis Waktu Eksponensial Kuat" bahwa waktu berjalan optimal untuk -SAT konvergen ke sebagai . Salah satu konsekuensi dari Strong-ETH adalah bahwa jawaban untuk pertanyaan di atas adalah tidak. Beberapa hipotesis masuk akal menyiratkan bahwa jawabannya adalah ya , tetapi siapa yang tahu.2 n k → $k$$2^{n}$$k \rightarrow \infty$

Saya pikir itu adalah salah satu masalah yang sepertinya akan "diselesaikan" dengan cara apa pun: entah kita akan menunjukkan jawaban ya, atau kita akan menunjukkan bahwa jawaban ya menyiratkan sesuatu yang sangat utama. Dalam kasus pertama, kita akan merasa puas untuk menyelesaikan masalah, dalam kasus kedua kita akan meningkatkan pertanyaan menjadi "masalah besar yang terbuka" ... jawaban tanpa menyiratkan , dan jawaban ya menyiratkan sesuatu yang sangat utama. :)$P \neq NP$

Pertanyaan apakah pohon keputusan dapat dipelajari PAC tampaknya berada di garis depan teori pembelajaran komputasi.

BUKA

Apakah decision tree (DTs) PAC dapat dipelajari di bawah distribusi seragam pada contoh (atau secara umum)?

DIKENAL

• DT tidak dapat dipelajari di bawah distribusi yang seragam dengan Statistik Query (SQs) [ Blum et al. '94 ]
• DT acak dapat dipelajari di bawah distribusi seragam [ Jackson, Servedio '05 ]
• DT monoton dapat dipelajari di bawah distribusi seragam [ O'Donnell, Servedio '06 ]
• analisis yang lancar untuk mempelajari DTs di bawah distribusi seragam [ Kalai, Teng '08 ]

Alasan ini adalah masalah yang menarik dan penting adalah karena pohon keputusan adalah kelas yang sangat alami, dan tidak seperti, katakanlah automata, kami tidak memiliki hasil kekerasan kriptografi yang membuat masalah menjadi sia-sia. Kemajuan pada pertanyaan ini mungkin dapat memberikan wawasan tentang apakah DT (dan kelas serupa) dapat dipelajari tanpa asumsi distribusi. Ini bisa memiliki dampak praktis selain menjadi terobosan teoretis.

Masalah ini juga tampaknya telah diatasi dari semua sisi. Kita tahu bahwa di bawah distribusi seragam pada contoh: pohon keputusan monoton dapat dipelajari, bahwa pohon keputusan acak dapat dipelajari, dan bahwa ada analisis yang diperhalus juga. Kami juga tahu bahwa algoritma SQ tidak akan menyelesaikan masalah ini. Dan ada juga kemajuan yang stabil di bidang ini. Di sisi lain, ini adalah masalah sulit yang telah terbuka untuk sementara waktu, jadi ini sepertinya sesuai dengan tagihan "Buka Masalah di Perbatasan TCS."

Perhatikan ada hasil lain yang saya tidak membahas tentang kekerasan DT belajar yang tepat , pada kemampuan untuk belajar DTs dengan pertanyaan , dan pada kekerasan belajar bahkan DTs acak dengan SQs.

BUKA:

Tunjukkan batas bawah dalam model probe sel untuk masalah struktur data statis eksplisit, yang membuktikan bahwa di bawah beberapa batasan ruang "masuk akal" (mis. Bahwa ruang polinomial dalam ukuran input), maka waktu kueri harus berada pada paling tidak T, di mana T lebih besar dari log | Q |, di mana Q adalah himpunan kueri. Ini disebut "log | Q | -barrier" (atau kadang-kadang, dengan cara yang agak salah, "logn-barrier").

DIKENAL:

1. batas bawah lebih tinggi dari log | Q | untuk masalah tersirat (lihat survei Miltersen )

2. batas bawah lebih tinggi dari log | Q | dengan batasan ruang yang ekstrim (mis. Batas bawah yang ringkas)

3. batas bawah lebih tinggi dari log | Q | untuk masalah dinamis (di mana saya maksudkan bahwa jika waktu pembaruan sangat kecil maka waktu permintaan harus sangat besar, atau sebaliknya; lihat misalnya batas bawah Patrascu untuk jumlah parsial)

4. Batas bawah dalam model terbatas, seperti mesin penunjuk, model perbandingan, dll

5. batas bawah yang memecahkan log | Q | penghalang tidak dapat dibuktikan dengan jenis pengurangan standar untuk kompleksitas komunikasi, karena Alice hanya dapat mengirim permintaan itu sendiri, yang hanya membutuhkan log | Q | bit, dan dengan demikian mudah untuk memverifikasi bahwa pengurangan tidak akan pernah memberikan batas bawah yang lebih baik daripada ini. Dengan demikian, "asli" yang terikat pada model probe sel harus digunakan, atau pengurangan yang lebih pintar untuk kompleksitas komunikasi harus digunakan.

Di kelas kompleksitas tingkat rendah, ada masalah yang menarik tentang karakterisasi .$\mathsf{NL}$

BUKA:

Tunjukkan bahwa apakah sama dengan .U $\mathsf{NL}$$\mathsf{UL}$

N $\mathsf{UL}$ , ruang log yang tidak ambigu , adalah kelas yang terdiri dari masalah yang dapat dipecahkan oleh -machine dengan kendala tambahan bahwa paling banyak ada satu jalur komputasi yang menerima.$\mathsf{NL}$

DIKENAL:

• Dalam keadaan yang tidak seragam , . [RA00]$\mathsf{NL/poly} = \mathsf{UL/poly}$
• Di bawah asumsi kekerasan yang masuk akal ( membutuhkan sirkuit ukuran eksponensial), hasil dari [RA00] dapat derandomized untuk menunjukkan bahwa . [ARZ99]N L = U $\mathsf{SPACE}(n)$$\mathsf{NL} = \mathsf{UL}$
• Reachability pada grafik 3 halaman selesai untuk . [PTV10]$\mathsf{NL}$
• Keterjangkauan pada grafik 2 halaman dapat dipecahkan untuk . [BTV09]$\mathsf{UL}$
• Jika , maka . [AJ93]$\mathsf{NL} = \mathsf{UL}$$\mathsf{FNL} \subseteq \mathsf{\sharp L}$

TIDAK DIKENAL:

• Kelas menengah , yang didefinisikan sebagai masalah yang dapat dipecahkan oleh -mesin dengan paling banyak secara polinomi menerima jalur komputasi, terletak di antara dan . Tidak ada keruntuhan yang diketahui.$\mathsf{FewL}$$\mathsf{NL}$$\mathsf{NL}$$\mathsf{UL}$
• Diketahui bahwa oleh Teorema Immerman-Szelepcsényi yang terkenal, sementara apakah ditutup dengan komplemen masih terbuka.$\mathsf{NL} = \mathsf{coNL}$$\mathsf{UL}$

Beberapa masalah PCP terbuka:

• Dugaan Skala Geser. Di PCP kami ingin kesalahan verifier sekecil mungkin. BGLR menduga bahwa kesalahan bisa sampai ke mana adalah keacakan (jelas ada batas bawah ). Harga yang Anda bayar untuk mengurangi kesalahan hanya meningkatkan alfabet dengan tepat.$2^{-\Theta(r)}$$r$$2^{-r}$

Lebih formal: dugaan adalah bahwa ada ac, sehingga untuk semua r alami, untuk semua , ada verifikasi PCP yang menggunakan r keacakan untuk membuat dua kueri menjadi buktinya, telah sempurna kelengkapan dan kesalahan kesehatan . Alfabet buktinya hanya bergantung pada .$\varepsilon \geq 2^{-cr}$$\varepsilon$$1/\varepsilon$

Untuk dua pertanyaan, kesalahan yang paling dikenal adalah untuk beberapa spesifik (M-Raz, 2008). Kita juga dapat mencapai kesalahan untuk , dengan sejumlah pertanyaan yang bergantung pada (DFKRS).$1/r^{\beta}$$\beta>0$$2^{-r^{\alpha}}$$\alpha <1$$\alpha$

Batas bawah pada c (yaitu, algoritma aproksimasi) juga dicari.

Lihat survei Irit Dinur untuk lebih jelasnya.

• PCP panjang linier. Ada kode koreksi kesalahan jarak tinggi dengan panjang linier. Apakah ada PCP dengan panjang linier?

Secara khusus, kami ingin verifier untuk pemenuhan formula SAT yang memiliki jumlah kueri, alfabet dan konstanta konstan yang konstan, dan mengakses bukti panjang linear dalam panjang rumus? Ini terbuka bahkan untuk kesalahan mendekati 1 (tapi lebih baik daripada trivial ), alfabet sub-eksponensial, dan jumlah kueri sub-linear.$1-1/n$

Panjang yang paling dikenal adalah untuk kesalahan konstan, dan untuk kesalahan sub-konstan.$n polylog n$$n \cdot 2^{(log n)^{1-\beta}}$

Buktikan bahwa untuk setiap , ada bahasa di yang tidak memiliki sirkuit (tidak seragam) dengan kabel . Ingatlah bahwa . Yaitu, buktikan sirkuit superlinear batas bawah untuk waktu eksponensial dengan akses ke oracle .$c > 0$$E^{NP}$$c n$$E = \bigcup_{k \geq 1} TIME[2^{k n}]$$NP$

A -locally decodable code (LDC) adalah peta sedemikian sehingga ada algoritma , yang disebut decoder lokal , yang, diberikan sebagai input integer dan kata diterima yang berbeda dari untuk beberapa paling banyak pecahan posisi, mencari paling banyak koordinat dan menghasilkan dengan probabilitas setidaknya . LDC dikatakan linier jika$(q,\delta,\epsilon)$$C: \mathbb{F}^m \to \mathbb{F}^n$$A$$i \in [m]$$y \in \mathbb{F}^n$$C(x)$$x \in \mathbb{F}^m$$\delta$$q$$y$$x_i$$1/|\mathbb{F}| + \epsilon$$\mathbb{F}$adalah bidang dan adalah -linear. LDC memiliki banyak aplikasi dalam teori kompleksitas dan privasi, antara lain.$C$$\mathbb{F}$

Untuk dan konstanta , situasinya benar-benar terselesaikan. Kode Hadamard adalah linier kueri LDC dengan , dan ini diketahui pada dasarnya optimal, bahkan untuk LDC non-linier. Tapi di sini, adalah perbatasan! Segera setelah kami membuat , ada kesenjangan besar antara batas atas dan bawah yang diketahui. Batas atas terbaik saat ini adalah LDC linear kueri di atas bidang terbatas apa pun (dan bahkan real dan kompleks) dengan kompleksitas kueri [ Efremenko '09 , Dvir-Gopalan-Yekhanin '10 ]. Batas bawah terbaik adalah$q=2$$\delta,\epsilon$$2$$n = \exp(m)$$q=2$$q=3$$3$$n=\exp(\exp(\sqrt{\log m \log \log m})) = 2^{m^{o(1)}}$$\Omega(m^2)$ untuk linear kueri LDC di atas bidang apa pun dan untuk umum kueri LDC [ Woodruff '10 ]. Situasi untuk jumlah pertanyaan yang lebih besar bahkan lebih mengerikan.$3$$\Omega(m^2/\log m)$$3$

Apa kesenjangan terbesar yang mungkin terjadi antara kompleksitas kueri deterministik dan (2-sided bounded-error) untuk fungsi total?

Buka:

Apakah ada fungsi total yang kompleksitas kueri kuantumnya adalah T, dan kompleksitas kueri deterministik adalah ω (T ² )?

Apakah ada fungsi total yang kompleksitas kueri kuantumnya adalah T, dan kompleksitas kueri deterministik adalah ω (T ⁴ )?

Jika fungsi total dapat dihitung dengan kueri T dengan algoritme kuantum, bisakah selalu dihitung dengan kueri dengan algoritme deterministik?$o(T^6)$

Dikenal:

Jika kompleksitas kueri kuantum dari fungsi total adalah T, kompleksitas kueri deterministiknya adalah . (Referensi)$O(T^6)$

Kesenjangan terbesar yang diketahui dicapai oleh fungsi OR, yang mencapai kesenjangan kuadratik.

Pembaruan (21 Juni 2015) : Kita sekarang tahu fungsi yang mencapai pemisahan kuartik (kekuatan 4). Lihat http://arxiv.org/abs/1506.04719 .

Dugaan bahwa fungsi OR mencapai kemungkinan celah maksimum.

Sesuai saran Ashley izinkan saya menambahkan masalah yang sama untuk perhitungan yang tepat.

Buka:

Apakah ada fungsi total yang memiliki kompleksitas kueri kuantum yang tepat adalah T, dan kompleksitas kueri deterministiknya adalah ?$\omega(T)$

Dikenal:

Jika kompleksitas kueri kuantum yang tepat dari fungsi total adalah T, kompleksitas kueri deterministiknya adalah . (Referensi)$O(T^3)$

Kesenjangan yang paling dikenal adalah faktor 2.

Pembaruan (5 Nov 2012) : Ini telah ditingkatkan dalam keunggulan Superlinear untuk algoritme kuantum yang tepat oleh Andris Ambainis . Dari abstrak: "Kami menyajikan contoh pertama dari fungsi Boolean f (x_1, ..., x_N) yang algoritma kuantum pastinya memiliki keunggulan superlinear dibandingkan dengan algoritma deterministik. Algoritma deterministik apa pun yang menghitung fungsi kami harus menggunakan N kueri tetapi algoritme kuantum yang tepat dapat menghitungnya dengan kueri O (N ^ {0,8675 ...}). "

Ada sejumlah masalah terbuka dalam kompleksitas bukti, saya hanya akan menyebutkan satu yang tetap terbuka bahkan setelah beberapa ahli menghabiskan waktu bertahun-tahun untuk menyelesaikannya. Ini adalah versi kompleksitas bukti keadaan dalam kompleksitas sirkuit. (Lihat [Segerlind07] jika Anda ingin melihat lebih banyak masalah terbuka dalam kompleksitas bukti.)

Buka

Buktikan lowerbounds ukuran bukti superpolinomial untuk sistem bukti -Bebas.$AC^0[2]$

$AC^0[2]$ -Frege (alias d-Frege + ) adalah sistem bukti proposisi yang hanya memungkinkan ( dengan gerbang) sirkuit.$CG_2$$AC^0[2]$$AC^0$$\bmod 2$

Diketahui

1. Ada lowerbound ukuran bukti eksponensial untuk -Frege (alias Frege kedalaman konstan, d-Frege) untuk (formulasi proporsional Prinsip Pigeon-Hole dengan merpati dan lubang). Ada juga lowerbounds eksponensial untuk -Frege + (Frege kedalaman konstan dengan penghitungan aksioma). Diketahui juga bahwa -Frege + tidak dibatasi secara polinomi.$AC^0$$PHP^{n+1}_{n}$$n+1$$n$$AC^0$$CA_p$$\bmod p$$AC^0$$CA_m$

2. Ada lowerbound ukuran sirkuit eksponensial untuk kelas sirkuit yang sesuai yaitu .$AC^0[2]$

Referensi:

• Nathan Segerlind, "Kompleksitas Bukti Proposisi", Buletin Simbolik Logika 13 (4), 2007

Buka:

Tampilkan pemisahan oracle antara QIP (2) dan AM. Artinya, menunjukkan masalah di QIP (2) ^A yang tidak di AM ^A .

Masalah besar yang terbuka adalah untuk menunjukkan pemisahan oracle antara BQP dan PH. Tetapi kami bahkan tidak memiliki pemisahan antara BQP dan AM (karena AM di PH, ini seharusnya lebih mudah). Lebih buruk lagi, buat BQP jauh lebih kuat dengan memungkinkan interaksi 1 putaran dengan Merlin, memberikan Anda kelas QAM atau QIP (2) (tergantung pada koin publik atau koin pribadi) dan kami masih belum memiliki pemisahan.

Dikenal:

Pemisahan yang paling dikenal adalah antara BQP dan MA, yang berasal dari makalah ini oleh John Watrous . Untuk kelas kompleksitas yang bukan kelas masalah keputusan, lihat hasil ini oleh Scott Aaronson .

Saya tidak yakin apakah ini milik kelas masalah terbuka perbatasan atau masalah terbuka besar , jadi komentar disambut.

Buka:

Tunjukkan bahwa apakah menyiratkan runtuh atau tidak.P $\mathsf{NP} = \mathsf{UP}$$\mathsf{PH}$

$\mathsf{UP}$ ( waktu polinom yang jelas ) adalah kelas yang didefinisikan sebagai masalah keputusan yang diputuskan oleh mesin-NP dengan batasan tambahan yang

• paling tidak ada satu jalur komputasi yang menerima input apa pun.

Masalah ini telah dinyatakan dalam kompleksitas blog pada tahun 2003.

Dikenal:

Sebuah hasil oleh Hemaspaandra, Naik, Ogiwara dan Selman menunjukkan bahwa jika pernyataan berikut memegang, maka hirarki polinomial runtuh ke tingkat kedua.

• Ada bahasa sehingga untuk setiap rumus di SAT, ada yang unik memuaskan tugas dengan di . L ϕ x ( ϕ , x ) $\mathsf{NP}$$L$$\phi$$x$$(\phi,x)$$L$

Tidak dikenal:

Setiap kemungkinan runtuh atau terpisah.

Posting terkait: Lebih lanjut tentang sintaksis vs kelas semantik, dan UP vs NP .