Apakah ada masalah NP, tidak dalam P dan tidak NP Lengkap?

34

Apakah ada masalah yang diketahui di (dan tidak di ) yang bukan Selesai? Pemahaman saya adalah bahwa saat ini tidak ada masalah yang diketahui, tetapi hal itu belum dikesampingkan sebagai suatu kemungkinan. P N PNPPNP

Jika ada masalah yaitu (dan bukan ) tetapi bukan , apakah ini merupakan akibat dari tidak ada isomorfisme yang ada antara instance dari masalah itu dan yang set? Jika hal ini, bagaimana kita tahu bahwa masalah tidak 'lebih keras' daripada apa yang saat ini kami identifikasi sebagai ?P N P - c o m p l e t e N P - c o m p l e t e N P N P - c o m p l e t eNPPNP-completeNP-completeNPNP-complete

vpiTriumph
sumber
1
Lihat juga pertanyaan terkait ini .
Raphael

Jawaban:

25

Apakah ada masalah yang diketahui di NP (dan bukan di P) yang tidak NP Lengkap? Pemahaman saya adalah bahwa saat ini tidak ada masalah yang diketahui, tetapi belum dikesampingkan sebagai suatu kemungkinan.

Tidak, ini tidak diketahui (dengan pengecualian bahasa sepele dan , keduanya tidak lengkap karena definisi banyak-satu pengurangan, biasanya keduanya diabaikan ketika mempertimbangkan banyak-satu pengurangan). Adanya masalah yang tidak lengkap untuk wrt many-one reduksi waktu polinomial akan menyiratkan bahwa yang tidak dikenal (meskipun secara luas diyakini) . Jika kedua kelas berbeda maka kita tahu bahwa ada masalah di yang tidak lengkap untuk itu, ambil masalah di .Σ N P N PΣNPNPN P PPNPNPP

Jika ada masalah yang NP (dan bukan P) tetapi tidak NP Lengkap, apakah ini merupakan hasil dari tidak ada isomorfisme antara contoh dari masalah itu dan set NP Lengkap?

Jika dua kelas kompleksitas berbeda maka dengan teorema Ladner ada masalah yang adalah -intermediate, yaitu mereka berada di antara dan .P N P - c o m p l e t eNPPNP-complete

Jika hal ini, bagaimana kita tahu bahwa masalah NP tidak lebih sulit dari apa yang saat ini kami identifikasi sebagai set NP Lengkap?

Mereka masih waktu polinomial direduksi menjadi masalah sehingga mereka tidak bisa lebih sulit dari masalah .N P - c o m p l e t eNP-completeNP-complete

Kaveh
sumber
Sudah beberapa tahun, tapi saya mendapat kesan bahwa masalah NP-Hard cocok dengan deskripsi OP, di mana mereka cocok?
Kevin
2
@Kevin: Tidak, NP-hard berarti masalah paling tidak sama sulitnya dengan masalah tersulit di NP.
Huck Bennett
Bagaimana dengan masalah dengan run-time psuedo-polinomial?
Joe
@ Jo, saya tidak yakin apa yang Anda maksud, jika Anda memiliki pertanyaan, posting sebagai pertanyaan baru.
Kaveh
1
Oh, tentu saja dengan asumsi P! = NP. Masalah seperti itu adalah Graph Isomorphism, kan?
levi
11

Seperti @Kaveh nyatakan, pertanyaan ini hanya menarik jika kita mengasumsikan ; sisa jawaban saya menganggap ini sebagai asumsi, dan sebagian besar menyediakan tautan untuk semakin membasahi nafsu makan Anda. Berdasarkan asumsi itu, menurut teorema Ladner kita tahu bahwa ada masalah yang tidak ada dalam atau ; masalah-masalah ini disebut -intermediate atau . Yang cukup menarik, teorema Ladner dapat digeneralisasi ke banyak kelas kompleksitas lainnya untuk menghasilkan masalah-masalah antara yang serupa. Lebih lanjut, teorema ini juga menyiratkan, bahwa ada hierarki tak terbatas dari masalah-masalah antara yang tidak dapat direduksi satu sama lain dalam .P N P C N P N P I N P IPNPPNPCNPNPINPI

Sayangnya, bahkan dengan asumsi sangat sulit untuk menemukan masalah alam yang dapat dibuktikan (tentu saja Anda memiliki masalah buatan yang berasal dari bukti teorema Ladner). Dengan demikian, bahkan dengan mengasumsikan saat ini kami hanya dapat mempercayai beberapa masalah sebagai tetapi tidak membuktikannya. Kami sampai pada keyakinan seperti itu ketika kami memiliki bukti yang masuk akal untuk percaya bahwa masalah tidak ada dalam dan / atau tidak dalam ; atau hanya ketika itu telah dipelajari untuk waktu yang lama dan menghindari masuk ke salah satu kelas. Ada daftar masalah yang cukup komprehensif dalam jawaban iniN P I P N P N P I N P N P C PPNPNPIPNPNPINPNPCP. Ini termasuk favorit sepanjang masa seperti anjak piutang, log diskrit, dan grafik-isomorfisme.

Menariknya, beberapa masalah ini (penting: factoring dan discrete log) memiliki solusi waktu polinomial pada komputer kuantum (yaitu mereka berada di ). Beberapa masalah lain (seperti grafik-isomorfisme) tidak diketahui berada dalam , dan ada penelitian yang sedang berlangsung untuk menyelesaikan pertanyaan. Di sisi lain, diduga bahwa , sehingga orang tidak percaya kita akan memiliki algoritma kuantum yang efisien untuk SAT (meskipun kita bisa mendapatkan kecepatan kuadratik); itu adalah pertanyaan yang menarik untuk dikhawatirkan tentang struktur seperti apa yang dibutuhkan agar berada dalam .BQPBQPN P I B Q PNPCBQPNPIBQP

Artem Kaznatcheev
sumber
Sebuah hasil yang benar-benar baru-baru ini oleh Babai (lihat jeremykun.com/2015/11/12/... ) memberikan algoritma quasipolynomial untuk grafik isomorfisme, pada dasarnya menghapusnya dari NPI, jika hasilnya bertahan. Menariknya, itu adalah masalah yang tidak diketahui berada di BQP
Frédéric Grosshans
1
@ FrédéricGrosshans yang memiliki algoritma kuasipolinomial waktu tidak menghapus Anda dari NPI (pada kenyataannya, itu bahkan tidak akan menghapus Anda dari NPC kecuali Anda membuat asumsi yang lebih kuat daripada hanya P! = NP). Hasil Babai (jika benar, yang mungkin benar) hanya memberikan bukti tidak langsung bahwa GraphIso mungkin ada di P, karena di masa lalu ketika algoritma quasipolynomial untuk masalah-masalah sulit ditemukan, mereka akhirnya mengarah ke algoritma polinomial.
Artem Kaznatcheev
1
@ FrédéricGrosshans Babai mencabut klaim runtime quasipolynomial . Ternyata ada kesalahan dalam analisis.
Raphael
@Raphael per komentar saya sebelumnya, saya tidak berpikir bahwa Babai bersantai quasipolynomial untuk subexponential tidak terlalu relevan dengan diskusi yang sedang berlangsung.
Artem Kaznatcheev
Karena komentar itu masih ada di sini, saya tidak ingin itu tidak dikoreksi. (Pada dasarnya, saya melacak semua kemunculan "Babai" di situs dan memposting komentar yang sama.) Jangan ragu untuk menandai semua komentar yang merasa sudah usang.
Raphael
7

Tidak ada NP masalah -Lengkap diketahui di P . Jika ada algoritma waktu polinomial untuk setiap masalah NP- lengkap, maka P = NP , karena setiap masalah dalam NP memiliki pengurangan waktu polinomial untuk setiap masalah NP- lengkap. (Itu sebenarnya bagaimana " NP- lengkap" didefinisikan.) Dan jelas, jika setiap masalah NP- lengkap terletak di luar P , ini berarti PNP . Kami tidak begitu yakin mengapa sulit untuk menunjukkannya dengan satu atau lain cara; jika kami tahu jawaban untuk pertanyaan itu, kami mungkin akan tahu lebih banyak tentang P danNP . Kami memiliki beberapa teknik pembuktian yang kami tahu tidak berfungsi (misalnya, relatifisasi dan pembuktian alami), tetapi tidak memiliki penjelasan prinsip mengapa masalah ini sulit.

Jika ada masalah dalam NP yang tidak dalam P , maka sebenarnya ada hirarki masalah tak terbatas dalam NP antara yang ada di P dan yang NP lengkap: ini adalah hasil yang disebut teorema Ladner .

Semoga ini membantu!

templatetypedef
sumber
tolong jelaskan: Tidak ada masalah dalam NP yang diketahui tidak ada di P? Bukankah semua P sudah ada di NP?
1
@ Shimano- Ini adalah dua konsep yang berbeda: Semua masalah dalam P diketahui dalam NP. Namun, kami tidak tahu apakah ada masalah dalam NP yang tidak ada dalam P. Artinya, kami tahu bahwa P adalah subset dari NP, tetapi kami tidak tahu apakah NP adalah subset dari P. Apakah itu menjelaskan hal-hal?
templatetypedef
Segalanya menjadi lebih jelas sekarang. Terima kasih banyak atas balasan cepat Anda. Diperlukan satu klarifikasi lagi. Anda berkata: "Alasan untuk ini adalah bahwa setiap masalah dalam NP memiliki pengurangan waktu polinomial untuk setiap masalah NP-complete." Ini membuktikan semua masalah dalam NP secara otomatis melengkapi-NP? Saya sedikit bingung lagi
@ Shimano- Tidak cukup. Arah pengurangan itu penting. Masalah adalah NP-complete jika semua masalah di NP mengurangi masalah itu. Anda juga dapat menunjukkan masalah adalah NP-hard dengan mengurangi masalah NP-complete yang diketahui untuk masalah itu. Namun, menunjukkan bahwa masalah dalam NP berkurang menjadi masalah NP-complete yang diketahui tidak menunjukkan sesuatu yang baru, karena menurut definisi semua masalah NP dikurangi menjadi semua masalah NP-complete.
templatetypedef
1
Teorema Shimano-Ladner mengatakan bahwa jika P! = NP, maka harus ada masalah NP-intermediate, jadi jika tidak ada masalah NP-intermediate, maka P = NP. Dan ya - jika kita dapat menemukan masalah dalam NP yang tidak dalam P, terlepas dari apakah itu dalam BQP, maka P! = NP.
templatetypedef
5

Ada beberapa masalah yang NP, tetapi tidak ada yang tahu mereka NP-Lengkap atau , seperti grafik isomorfisma 1 . Tapi seperti yang saya tahu tidak ada kelas kompleksitas khusus untuk masalah seperti itu, mungkin saya salah.P

Mungkin itu , misalnya sebelum algoritma AKS tidak ada yang tahu pengujian primality adalah atau NPC.PPP

Juga ada beberapa masalah yang NPC tetapi tidak dalam arti kuat atau lemah NP-Lengkap , seperti masalah 2-Partisi , berarti, jika nomor input dalam urutan polinomial ukuran input, masalah ini dapat diselesaikan dalam (atau ada algoritma waktu polinomial semu untuk mereka).P


1 Masalah serupa: isomorfisma sub grafik adalah NP-Lengkap dalam arti kuat.


sumber
3 tahun kemudian, grafik-isomorfisme tampaknya sangat dekat dengan P (algoritma waktu quasipolynial telah diusulkan oleh Babai) jeremykun.com/2015/11/12/…
Frédéric Grosshans
Babai mencabut klaim runtime quasipolynomial . Ternyata ada kesalahan dalam analisis.
Raphael
Kesalahan dalam bukti Babai diperbaiki beberapa hari kemudian.
David Bevan