Konsekuensi dari masalah lengkap untuk NP memotong CoNP

24

Apa konsekuensi dari memiliki masalah lengkap dalam ?NPcoNP

Marcos Villagra
sumber
Lihat juga mathoverflow.net/questions/34889/…
Jukka Suomela
Saya tahu tautan itu. Pertanyaan saya adalah tentang konsekuensinya. Misalnya, jika bahasa L selesai untuk maka PH runtuh ke tingkat ke- i , atau sesuatu seperti itu. NPcoNPi
Marcos Villagra
Sebenarnya, saya mengajukan pertanyaan yang sama dengan komentar di tautan itu, tetapi saya ingin membuatnya menjadi pertanyaan nyata.
Marcos Villagra
2
Ya, saya tahu Anda tahu, tetapi halaman mathoverflow memberikan informasi latar belakang yang bermanfaat bagi orang lain.
Jukka Suomela

Jawaban:

18

Ini adalah masalah terbuka (lebar); seperti dalam, kita hampir tidak tahu apa-apa. Secara khusus, karena sulitnya membuktikan NPcoNP -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 membuktikan NPcoNP menyelesaikan masalah dan menambahkan pemikiran saya:

Saat ini, kami hanya memiliki "lemah," calon alami untuk keanggotaan di NPcoNPP 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 poly(n)2klog(k) . (Jika ada masalah lengkap dalamNPcoNPP, makaapakah sub-eksponensial(tidak murni eksponensial, atau cukup polinomial)runtime endemik dari kelas?)

Jadi khusus, kami ingin membuktikan sesuatu seperti: masalah A hanya di P IFF NPcoNP=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) sepertiPSPACE dan#P .

Kesulitan, bagaimanapun, dengan memberikan representasi yang sama untuk NPcoNP adalah bahwa "alam" analog memungkinkan kita untuk menanamkan Soal terputus-putus dalam representasi dan karena itu diputuskan . Artinya, pertimbangkan upaya berikut untuk mewakili NPcoNP dengan dua mesin Turing non-deterministik yang, konon, mengenali bahasa pelengkap:

Pertanyaan: Apakah Mesin Turing M berhenti pada input x0,1n ?

Buat dua mesin Turing linear-waktu M1 dan M2 sebagai berikut. Pada input y , M1 membaca input dan selalu menerima. M2 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" dari NPcHaiNP masalah tidak dapat dikenali polinomial-waktu. Pertanyaan sisa: Bagaimana Anda mewakili NPcHaiNP 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 di NPcHaiNP . Oleh karena itu, saya mengklaim bahwa keberadaan teknik bukti yang dapat menyelesaikan kelengkapan NPcHaiNP akan menjadi cerita yang lebih besar di sini - bukan hasil "otomatis" dari NPcHaiNP - masalah lengkap ( misalnya kelas kompleksitas, mungkin runtuh) yang sudah kita sadari (atau lebih tepatnya, akan sadari , secara hipotesis di masa depan).

Daniel Apon
sumber
1
terima kasih untuk PDFnya. Belum membacanya tetapi saya akan membacanya. Ada makalah ini: "Pada fungsi total, teorema keberadaan dan kompleksitas komputasi". Nimrod Megiddo dan Christos Papadimitriou. Ilmu Komputer Teoritis 81, 1991. Ini bukan tentang , tetapi kelas fungsi yang terkait TFNP, yaitu T F N P = F ( N P c o N P ) . Ada teorema berikut: "Ada masalah lengkap FNP di TFNP iff NP = coNP". Mengingat bahwa masalah pencarian dan keputusan terkait secara polinomi, apakah teorema ini juga meluas ke N PNPcHaiNPTFNP=F(NPcHaiNP) ? Jika demikian, ini akan menyiratkan penurunan besar dalam PH. Apakah ini benar? NPcHaiNP
Marcos Villagra
Ini tidak secara langsung diterjemahkan (dengan cara yang saya yakini Anda maksudkan). Perhatikan bahwa teorema tidak merujuk hanya ke masalah APAPUN lengkap, tetapi masalah lengkap FNP. Ini sama dengan mengatakan "Ada masalah NP-complete di NP \ cap coNP iff NP = coNP." Sejauh yang saya ketahui, dapat dibayangkan bahwa NP \ cap coNP memiliki masalah lengkap yang berbeda dari masalah NP-complete, tanpa PH kolaps . (Tautan untuk bersenang-senang.;))
Daniel Apon
Catatan: Masih dianggap tidak mungkin bahwa situasi yang saya jelaskan di atas sebagai yang mungkin terjadi adalah alasan yang sama dalam jawaban.
Daniel Apon