Kelas kompleksitas komputasi dan hubungannya
Norbert Blum baru-baru ini diposting 38-halaman bukti bahwa P≠NPP≠NPP \ne NP . Apakah itu benar? Juga pada topik: di mana lagi (di internet) kebenarannya sedang dibahas? Catatan: fokus teks pertanyaan ini telah berubah seiring waktu. Lihat komentar pertanyaan untuk
Pertanyaan ini adalah sesuatu yang sudah lama saya tanyakan. Ketika orang menggambarkan masalah P vs NP, mereka sering membandingkan NP kelas dengan kreativitas. Mereka mencatat bahwa menyusun simfoni kualitas Mozart (analog dengan tugas NP) tampaknya jauh lebih sulit daripada memverifikasi bahwa...
Dalam Kompleksitas Deskriptif , Immerman memiliki Konsekuensi 7.23. Kondisi berikut ini setara: 1. P = NP. 2. Struktur yang terbatas, terurut, FO (LFP) = SO. Ini dapat dianggap sebagai "memperkuat" P = NP untuk pernyataan yang setara atas (mungkin) kelas kompleksitas yang lebih besar....
Kita tahu bahwa L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} dan L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , di mana L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Kita juga tahu bahwa...
Sejauh yang saya mengerti, upaya Program teori kompleksitas geometri untuk memisahkan dengan membuktikan bahwa permament dari matriks bernilai kompleks adalah jauh lebih sulit untuk menghitung dari determinan.VP≠VNPVP≠VNPVP \neq VNP Pertanyaan yang saya miliki setelah membaca sekilas tentang GCT...
Kelas kompleksitas terdiri dari masalah-masalah yang dapat diputuskan oleh mesin Turing waktu polinomial nondeterministic yang memiliki paling banyak satu yang menerima jalur komputasi. Artinya, solusinya, jika ada, unik dalam pengertian ini. Diperkirakan sangat tidak mungkin bahwa semua masalah...
Semakin kompleksnya program komputer dan semakin pentingnya posisi komputer dalam masyarakat kita membuat saya bertanya-tanya mengapa kita masih belum secara kolektif menggunakan bahasa pemrograman di mana Anda harus memberikan bukti formal bahwa kode Anda berfungsi dengan benar. Saya percaya...
Dalam pengantar dan penjelasan kompleksitas P dan NP sering diberikan melalui mesin Turing. Salah satu model perhitungan adalah lambda-calculus. Saya mengerti, bahwa semua model perhitungan adalah setara (dan jika kita dapat memperkenalkan apa pun dalam istilah mesin Turing, kita dapat...
Dalam bukunya "Kompleksitas Komputasi", Papadimitriou menulis: Dalam beberapa hal RP adalah jenis kompleksitas yang baru dan tidak biasa. Tidak ada mesin Turing nondeterministik terikat polinomi dapat menjadi dasar mendefinisikan bahasa dalam RP. Agar mesin N mendefinisikan bahasa dalam RP , ia...
Dari sudut akal sehat pandang, mudah untuk percaya bahwa menambahkan non-determinisme ke secara signifikan memperluas kekuasaannya, yaitu, N P jauh lebih besar dari P . Bagaimanapun juga, non-determinisme memungkinkan paralelisme eksponensial, yang nampaknya sangat kuat. PP\mathsf{P}N...
Sebagai seorang amatir TCS, saya membaca beberapa materi yang sangat populer tentang komputasi kuantum. Berikut adalah beberapa informasi dasar yang telah saya pelajari sejauh ini: Komputer kuantum tidak dikenal untuk menyelesaikan masalah NP-complete dalam waktu polinomial. "Sihir kuantum tidak...
Pertimbangkan masalah penghitungan berikut (atau masalah keputusan terkait): Diberi dua bilangan bulat positif yang dikodekan dalam biner, hitung pembagi bersama terbesarnya (gcd). Apa kelas kompleksitas terkecil dari masalah ini? Bisakah Anda memberikan referensi? Dalam pertanyaan ini saya...
Masalah utama dari teori kompleksitas ini bisa dibilang vs N P .PPPNPNPNP Namun, karena Alam adalah kuantum, akan terlihat lebih alami untuk mempertimbangkan kelas (masalah yaitu keputusan dipecahkan oleh sebuah komputer kuantum dalam waktu polinomial, dengan probabilitas kesalahan paling 1/3...
Pertanyaan ini adalah tentang masalah yang ada celah kompleksitas terbuka yang besar antara batas bawah yang diketahui dan batas atas, tetapi bukan karena masalah terbuka pada kelas kompleksitas itu sendiri. Untuk lebih tepatnya, katakanlah masalah memiliki kelas gap A,BA,BA,B (dengan...
Dalam makalah The Random Oracle Hypothesis Is False , penulis (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, dan Rohatgi) membahas implikasi dari hipotesis oracle acak . Mereka berpendapat bahwa kita tahu sedikit tentang pemisahan antara kelas kompleksitas, dan sebagian besar hasil melibatkan...
Ada justifikasi filosofis yang sering dikutip untuk meyakini bahwa P! = NP bahkan tanpa bukti. Kelas kompleksitas lainnya memiliki bukti bahwa mereka berbeda, karena jika tidak, akan ada konsekuensi "mengejutkan" (seperti runtuhnya hierarki polinomial). Pertanyaan saya adalah, apa dasar untuk...
Ada banyak masalah NP-selesai di sekitar dan sumber mengumpulkan mereka, misalnya lihat buku oleh Garey dan Johnson. Saya akan tertarik untuk melihat daftar masalah lengkap NEXP juga. Apakah ada satu tersedia? Karena saya anggap tidak ada, saya membuka pertanyaan ini (apakah ini seharusnya...
Apa konsekuensi buruk NP = PSPACE? Saya terkejut saya tidak menemukan apa-apa tentang ini, mengingat bahwa kelas-kelas ini adalah yang paling terkenal. Secara khusus, apakah akan ada konsekuensi pada kelas
NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}P ≠ N P N P I : = N P ∖ ( N P C ∪ P ) ≠ ∅ P / poli N P I ⊂ P / poli N P ⊂ N P C ∪ P / poliPH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne \mathsf{NP}NPI:=NP∖(NPC∪P)≠∅NPI:=NP∖(NPC∪P)≠∅\mathsf{NPI} := \mathsf{NP}...
Misalkan P = NP benar. Apakah kemudian akan ada aplikasi praktis untuk membangun komputer kuantum seperti memecahkan masalah tertentu lebih cepat, atau akankah perbaikan seperti itu menjadi tidak relevan berdasarkan fakta bahwa P = NP benar? Bagaimana Anda mengkarakterisasi peningkatan efisiensi...