Apakah ada masalah "NP-Menengah-Lengkap"?

13

Asumsikan P NP.≠

Teorema Ladner mengatakan bahwa ada masalah NP Menengah (masalah dalam NP yang tidak dalam P atau NP-Lengkap). Saya telah menemukan beberapa referensi terselubung online yang menyarankan (saya pikir) bahwa ada banyak "level" dari bahasa yang saling direduksi dalam NPI yang pasti tidak semuanya runtuh menjadi satu.

Saya punya beberapa pertanyaan tentang struktur level-level ini.

  1. Apakah ada masalah "NP-Intermediate-Complete" - yaitu, masalah NP-Intermediate dimana setiap masalah NP-Intermediate lainnya dapat direduksi poliwaktu?
  2. Urutkan NP - P ke dalam kelas kesetaraan, di mana reducibilitas timbal balik adalah hubungan kesetaraan. Sekarang memaksakan pemesanan pada kelas-kelas kesetaraan ini: jika masalah dalam mengurangi menjadi masalah dalam (jadi jelas kelas kesetaraan NP-Complete adalah elemen maksimum). Apakah ini pemesanan total (mis. Masalahnya diatur dalam rantai menurun tak terbatas)? Jika tidak, apakah "struktur pohon" dari pemesanan parsial memiliki faktor percabangan yang terbatas?B AA>BBA
  3. Apakah ada komponen struktural menarik lainnya yang diketahui dari NP - P? Apakah ada pertanyaan terbuka yang menarik tentang struktur yang mendasarinya?

Jika salah satu dari ini saat ini tidak diketahui, saya akan tertarik untuk mendengarnya juga.

Terima kasih!

cc.complexity-theory np np-intermediate GMB
sumber
3
Versi lemah dari ini adalah bahwa ada masalah "Graph-Isomorphism-Complete".
Suresh Venkat
7
Jawaban untuk 1. adalah "ya dan tidak" Saya pikir: Ya karena seperti yang dikatakan Suresh, Anda dapat memiliki masalah lengkap-GI (dan -lengkap masalah untuk masalah lain ). Dan tidak karena oleh bukti Ladner, ada hirarki tak terbatas kelas dan jika saya tidak salah, memiliki masalah -intermediate-complete akan meruntuhkan hierarki ini (dan dengan demikian dengan kontradiksi membuktikan ), dengan cara yang sama dengan hierarki polinomial tidak dapat memiliki masalah lengkap jika tidak runtuh. π N P N P P = N PππNPNPP=NP
Bruno
Terima kasih, Bruno - dapatkah info ini ditemukan di koran asli Ladner, atau haruskah ada sumber lain yang relevan?
GMB
Anda juga dapat melihat kertas Downey dan Fortnow: Bahasa Seragam Keras ; di mana bukti teorema Ladner yang diberikan dalam Lampiran A.1 menunjukkan bahwa derajat waktu polinomial dari bahasa yang dapat dikomputasi adalah urutan parsial yang padat. Mereka juga menduga bahwa jika ada set hard seragam di NP maka ada set hard seragam seragam.
Marzio De Biasi
1
untuk referensi lain untuk 1. dan sumber daya yang mungkin bermanfaat, lihat jawaban Ryan , dan makalah Schoening yang dikutip di dalamnya.
Sasho Nikolov

Jawaban:

31

Saya tidak memiliki referensi untuk hasil ini - mereka tidak sulit untuk dibuktikan begitu Anda memahami teorema Ladner.

  1. Tidak, untuk setiap set NP-tidak lengkap A ada set B lain antara A dan SAT.

  2. Kelas-kelas ekivalensi ini dikenal sebagai polinomial-banyak-satu derajat. Anda dapat menanamkan setiap posite terbatas ke dalam derajat di bawah NP. Secara khusus derajat tidak sepenuhnya dipesan atau bercabang secara halus.

  3. Ini semua tergantung pada apa yang Anda maksud dengan "menarik". Ada teori besar tentang struktur derajat set yang dapat dihitung (lihat buku Soare misalnya) dan banyak dari pertanyaan itu belum dimasukkan ke set waktu polinomial. Misalnya, dapatkah Anda memiliki set NP A dan B yang join-nya setara dengan SAT dan yang meet-nya setara dengan set kosong?

Lance Fortnow
sumber
1
Apa yang Anda maksud dengan pertemuan, semacam persimpangan? Saya kira gabungan dari dan adalah sedemikian sehingga iff dan , apakah itu benar? B C ( x , y ) ∈ C x ∈ A y ∈ BABC(x,y)∈Cx∈Ay∈B
John D.
8
Ini adalah istilah teori kisi : gabungan dari subset adalah batas atasnya yang paling rendah (jika ada) dan memenuhi batas bawah terbesar.
Bruno