Apa konsekuensi dari memiliki masalah lengkap dalam ?
cc.complexity-theory
conditional-results
Marcos Villagra
sumber
sumber
Jawaban:
Ini adalah masalah terbuka (lebar); seperti dalam, kita hampir tidak tahu apa-apa. Secara khusus, karena sulitnya membuktikanNP∩ c o NP -lengkap masalah, kita membutuhkan teknik bukti yang sangat berbeda dari yang ada saat ini. Dengan demikian, diskusi tentang konsekuensi harus secara wajar menyertakan garis singgung pada "Apa artinya memiliki teknik pembuktian baru yang begitu kuat dan baru?"
Untuk diskusi yang relatif baru tentang topik ini, ada kolom NP-Completeness ke-26 David Johnson dalam ACM Transactions on Algorithms from 2007 ( PDF ). Ijinkan saya untuk memparafrasekan apa yang dikatakan David mengenai pertanyaan untuk membuktikanNP∩ c o NP menyelesaikan masalah dan menambahkan pemikiran saya:
Saat ini, kami hanya memiliki "lemah," calon alami untuk keanggotaan diNP∩ c o NP- P dalam arti bahwa yang terkuat bukti untuk keanggotaan mereka adalah bahwa kami belum berhasil menemukan algoritma waktu polinomial untuk mereka belum. Dia mendaftar beberapa kandidat: FAKTOR KECIL, GAME STOCHASTIC SEDERHANA, dan GAME MEAN PAYOFF. Beberapa "keanehan" tambahan dari masalah ini berasal dari waktu proses heuristik terbaik untuk menyelesaikannya, misalnya FAKTOR KECIL, alias FAKTOR INTEGER ≤ k , memiliki kompleksitas waktu acak p o l y( n ) 2k l o g( k )√ . (Jika ada masalah lengkap dalamNP∩ c o NP- P , makaapakah sub-eksponensial(tidak murni eksponensial, atau cukup polinomial)runtime endemik dari kelas?)
Jadi khusus, kami ingin membuktikan sesuatu seperti: masalah A hanya diP IFF NP∩ c o NP= P , yaitu hasil kelengkapan seperti teorema Cook untuk 3SAT dan NP . Untuk NP , bukti semacam itu secara universal melibatkan pengurangan waktu polinomial (dan perbaiki favorit Anda, batasan tambahan, misalnya pengurangan Cook, reduksi Karp). Akibatnya, di bawah teknik reduksi waktu polinomial, harus ada kasus bahwa terdapat representasi kelas polinomial waktu yang dapat dikenali. Untuk NP , kita dapat menggunakan mesin Turing non-deterministik yang berhenti dalam polinomial, p ( | x | ) , jumlah langkah. Seperti yang ditunjukkan David keluar, kita memiliki representasi yang sama untuk kelas-kelas lain (di mana status yang lebih jelas) sepertiPSPA CE dan#P .
Kesulitan, bagaimanapun, dengan memberikan representasi yang sama untukNP∩ c o NP adalah bahwa "alam" analog memungkinkan kita untuk menanamkan Soal terputus-putus dalam representasi dan karena itu diputuskan . Artinya, pertimbangkan upaya berikut untuk mewakili NP∩ c o NP dengan dua mesin Turing non-deterministik yang, konon, mengenali bahasa pelengkap:
Pertanyaan: Apakah Mesin TuringM.∗ berhenti pada input x ∈ 0 , 1n ?
Buat dua mesin Turing linear-waktuM.1 dan M.2 sebagai berikut. Pada input y , M.1 membaca input dan selalu menerima. M.2 selalu menolak kecuali | y| ≥ | x | dan M.∗ menerima x dalam langkah ≤ | y| .
Oleh karena itu,M.1 dan M.2 menerima bahasa pelengkap jika M.∗ tidak berhenti pada input x . Oleh karena itu, dengan kontradiksi, memutuskan apakah dua mesin Turing polinomial waktu menerima bahasa pelengkap tidak dapat diputuskan.
Jadi, representasi "alami" dariNP∩ c o NP masalah tidak dapat dikenali polinomial-waktu. Pertanyaan sisa: Bagaimana Anda mewakili NP∩ c o NP masalah seperti bahwa mereka adalah polinomial-waktu dikenali?
Belum ada pekerjaan yang signifikan dilakukan pada masalah ini, namun resolusi yang sukses diperlukan untuk membuktikan kelengkapan diNP∩ c o NP . Oleh karena itu, saya mengklaim bahwa keberadaan teknik bukti yang dapat menyelesaikan kelengkapan NP∩ c o NP akan menjadi cerita yang lebih besar di sini - bukan hasil "otomatis" dari NP∩ c o NP - masalah lengkap ( misalnya kelas kompleksitas, mungkin runtuh) yang sudah kita sadari (atau lebih tepatnya, akan sadari , secara hipotesis di masa depan).
sumber