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

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 $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$

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 $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP\text{-}complete}$$\mathsf{NP\text{-}complete}$$\mathsf{NP}$$\mathsf{NP\text{-}complete}$

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 $\emptyset$$\Sigma^*$$\mathsf{NP}$$\mathsf{NP}$N P $\mathsf{P}\neq\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}$

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 $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP\text{-}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 $\mathsf{NP\text{-}complete}$$\mathsf{NP\text{-}complete}$

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 $P \neq NP$$P$$NPC$$NP$$NPI$$NPI$

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 $P \neq NP$$NPI$$P \neq NP$$NPI$$NP$$NPC$$P$. 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 .$BQP$$BQP$N P I B Q P$NPC \not\subseteq BQP$$NPI$$BQP$

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 P ≠ NP . 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!

Ada beberapa masalah yang NP, tetapi tidak ada yang tahu mereka NP-Lengkap atau , seperti grafik isomorfisma ¹ . 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.$P$$P$

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$

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