Masalah NP-complete tidak "jelas" di NP

27

Terlintas dalam banyak hal bahwa dalam semua bukti -completeness yang saya baca (yang dapat saya ingat), selalu sepele untuk menunjukkan bahwa masalahnya ada di , dan menunjukkan bahwa itu adalah -hard adalah ... bagian yang sulit. Apa masalah lengkap yang verifier waktu polinomialnya sangat tidak sepele? $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$

complexity-theory np-complete np kepala kebun
sumber

9

Bukan NP-complete, tetapi menunjukkan keanggotaan dalam NP untuk menguji apakah suatu bilangan prima cukup non-sepele (daripada menunjukkan bahwa itu adalah komposit, yang sepele). Masalahnya tentu saja diketahui berada di P sekarang, tetapi tetap saja, ini adalah verifikasi yang menarik.

Shaull

2

Membuktikan "PRIME" dalam NP jelas jauh lebih sulit daripada membuktikan bahwa sebagian besar masalah NP-lengkap ada di NP.

gnasher729

1

Lihat juga pertanyaan umum cstheory.stackexchange.com/q/21106/109 di CS.SE.

András Salamon

19

Setidaknya ada empat seperti masalah -Lengkap tercantum dalam lampiran Garey dan Johnson Komputer dan kedegilan: A Guide to Teori NP-Kelengkapan . $NP$

[AN6] TIDAK DIVISIBILITAS DARI POLINOMIAL PRODUK

Instance: Urutan dari pasangan bilangan bulat, dengan masing-masing dan integer . $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ $b_i[j] \geqslant 0,$ $N$

PERTANYAAN: Apakah tidak habis dibagi ? $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ $z^N - 1$

Referensi: [Plaisted, 1977a] , [Plaisted, 1977b] . Transformasi dari 3SAT. Bukti keanggotaan dalam NP adalah non-sepele dan muncul dalam referensi kedua.

Tiga lainnya yang saya temukan dalam lampiran adalah:

[LO13] LOGIC LOGIC S5-SATISFIABILITY
[LO19] PEMESANAN KEDUA KEDUA
[MS3] NON-LIVENESS DARI PILIHAN GRATIS JARINGAN PETRI

Kyle Jones
sumber

Terima kasih! Saya memiliki buku ini jadi saya akan memastikan untuk memeriksanya.

gardenhead

Saya agak tidak jelas mengenai masalah ini: (1) Apakah saya benar dalam menafsirkan z adalah variabel yang dapat mengambil nilai integer (seperti persamaan linear / kuadratik biasa). (2) Dengan demikian, non-dibagi akan setara dengan menyatakan bahwa: "tanpa nilai integer dari persamaan z A dapat dibagi oleh B"?

TheoryQuest1

1

Apa yang saya kumpulkan dari membaca beberapa halaman pertama makalah 1977a adalah bahwa

adalah jumlah yang berhubungan dengan jumlah nol dari polinomial yang merupakan bagian dari input. Untuk lebih dari itu, aku harus merogoh kertas, aku khawatir.

z

$z$

Kyle Jones

4

Berikut adalah masalah dari teori database, lebih spesifik, dari teori serializability.

Dalam Serializability by Locking (Halaman 237) , dikatakan bahwa

Mengenai kompleksitas keamanan, Papadimitriou et al. [14] menunjukkan bahwa -hard untuk menguji apakah sistem transaksi bukan safe, dan menduga bahwa masalahnya adalah . Dari Teorema 3 (Dalam makalah ini), dapat disimpulkan bahwa ini benar. $\textrm{NP}$ $SSR$ $\textrm{NP}$

Masalah -aman dapat ditemukan di kertas "Beberapa Masalah Komputasi Terkait dengan Kontrol Concurrency Database" oleh Papadimitriou et al. Sayangnya, saya tidak memiliki akses ke sana. $SSR$

Hengxin
sumber

2

Bagi saya, Integer Linear Programming (dan Aritmatika Presburger Gratis Quantifier terkait) ada di kelas ini.

Pendekatan naif untuk masalah ILP dimensi adalah untuk beralih melalui semua panjang vektor bilangan bulat. Tapi ini adalah proses tanpa batas. $n$ $n$

Anda harus menggunakan beberapa teori bilangan untuk membuktikan bahwa ada batas atas polinomial pada ukuran solusi, yang berarti bahwa jika ada solusi, selalu ada solusi berukuran polinomi, yang bertindak sebagai sertifikat.

Informasi lebih lanjut dapat ditemukan dalam jawaban atas pertanyaan yang saya ajukan beberapa waktu lalu.

Ya ampun
sumber

Masalah NP-complete tidak "jelas" di NP

Jawaban: