Masalah NP-Hard yang tidak ada dalam NP tetapi dapat ditentukan

31

Saya bertanya-tanya apakah ada contoh yang baik untuk masalah NP-Hard yang mudah dipahami yang bukan NP-Lengkap dan tidak diputuskan?

Misalnya, masalah penghentian adalah NP-Hard, bukan NP-Complete, tetapi tidak dapat dipastikan.

Saya percaya bahwa ini berarti bahwa ini merupakan masalah yang dapat diverifikasi solusinya tetapi tidak dalam waktu polinomial. (Tolong, perbaiki pernyataan ini jika ini bukan masalahnya).

diri
sumber
Melihat sekilas kerumitan kebun binatang membuat pertanyaan ini terasa konyol - ada begitu banyak kelas antara NP dan R! Tentu saja, kita tidak tahu semua inklusi harus ketat, jadi ada sesuatu yang menarik di sini.
Raphael

Jawaban:

33

N E X P N P N E X P N P N E X PNPNEXPNEXPNPNEXPNPNEXP

  • 3-colourability dari grafik yang dijelaskan oleh sirkuit ringkas - atau masalah NP-lengkap lainnya pada grafik - di mana "sirkuit ringkas" adalah format untuk mewakili grafik yang sangat besar pada input: alih-alih representasi eksplisit dari grafik misalnya  dengan daftar adjacency, sebaliknya, kami menyediakan sirkuit yang menghitung beberapa fungsi yang menghitung koefisien dari matriks kedekatan.2 n × 2 nf:{0,1}n×{0,1}n{0,1}2n×2n

  • (Non-) ekivalen dari dua ekspresi reguler, di mana bintang Kleene digantikan oleh kuadrat (mengulangi sub-pola tepat dua kali, bukan nol atau lebih kali), dan di mana kami bertanya apakah dua ekspresi reguler tersebut mewakili rangkaian string yang berbeda.

Perhatikan bahwa dalam kasus terakhir, jika kita mengambil ekspresi reguler seperti yang biasa kita pertimbangkan, termasuk bintang Kleene, masalah yang dihasilkan adalah -complete: karena kita memiliki kontainmen , ini masih merupakan masalah yang dapat yaitu -hard, dan bukan dalam .N PN E X PE X P S P A C E N P N PEXPSPACENPNEXPEXPSPACENPNP

Niel de Beaudrap
sumber
7

Penafian: Jawaban ini didasarkan pada asumsi bahwa , sebuah hipotesis yang diyakini sebagian besar ilmuwan, tetapi kami belum membuktikannya. Ini berarti bahwa ada kemungkinan bahwa masalah ini ada di dan karenanya juga -complete.NP NPPSPACENPNPNP

Saya akan mengatakan yang paling sederhana adalah rumus Boolean True quantified dan General geography , keduanya -complete.PSPACE

TQBF diberikan rumus boolean yang dikuantifikasi , uji apakah rumus itu benar, yaitu rumus pada formulir salah, karena pengaturan ke false menghasilkan pernyataan salah.zxyz.[(xy)z]z

Generalised Geography adalah permainan yang menyenangkan (lihat rantai kata ) di mana Anda memiliki daftar string (mis. Nama kota) dan Player 1 dimulai dengan mengucapkan nama, dan Player 2 merespons dengan nama yang dimulai dengan huruf yang diakhiri dengan nama sebelumnya. Kemudian giliran Pemain 1, hingga seseorang terjebak (permainan ini disarankan untuk dimainkan sebagai permainan minum di mana objek adalah band / artis, film, kota, ibukota, ahli matematika terkenal atau apa pun yang mengapung perahu Anda. Orang yang tidak dapat merespons dalam waktu yang wajar tentunya harus minum). Masalah formal dinyatakan sebagai pertanyaan "apakah Pemain 1 memiliki strategi kemenangan" .

Pål GD
sumber
9
Saya tidak benar-benar berpikir jawaban ini adalah tepat, karena ada kelas yang kita lakukan tahu secara ketat atas NP yang dapat melayani. Paling tidak, Anda harus merevisi jawaban Anda sehingga, alih-alih catatan akhir Anda di akhir, Anda bisa mengatakan sebaliknya di awal jawaban Anda bahwa jawaban Anda bergantung pada (sebuah ketidaksetaraan yang kami yakini mungkin benar). --- Komentar ini adalah pengganti dari komentar yang saya hapus sebelumnya; maaf untuk spam. NPPSPACE
Niel de Beaudrap