Apakah set NP-complete dibentuk dari dua set lainnya hanya jika setidaknya satu NP-hard?

Pertanyaan ini agak bertentangan dengan pertanyaan sebelumnya pada set yang dibentuk dari set operasi pada set NP-complete:

Jika himpunan yang dihasilkan dari gabungan, persimpangan, atau produk Cartesian dari dua himpunan yang dapat ditentukan dan adalah NP-complete, apakah paling tidak salah satu dari tentu NP-hard? Saya tahu mereka tidak bisa keduanya dalam P (dengan asumsi P! = NP) karena P ditutup di bawah operasi yang ditetapkan ini. Saya juga tahu bahwa kondisi "decidable" dan "NP-hard" diperlukan karena jika kita mempertimbangkan setiap NP-complete set dan set luar NP (apakah hanya NP-hard atau undecidable) maka kita dapat membentuk dua NP-hard set tidak dalam NP yang simpanginya NP-complete. Misalnya: $L_1$ $L_2$ $L_1, L_2$ $L$ $B$ , dan . Namun, saya tidak tahu bagaimana melanjutkan setelah itu. $L_1:= 01L \cup 11B$ $L_2:= 01L \cup 00B$

Aku berpikir bahwa kasus union mungkin tidak benar karena kita bisa mengambil set NP-lengkap dan melakukan pembangunan di Ladner Teorema untuk mendapatkan satu set NPI yang merupakan subset dari . Kemudian adalah set NP-complete yang asli. Namun, saya tidak tahu apakah masih dalam NPI atau NP-hard. Saya bahkan tidak tahu harus mulai dari mana untuk persimpangan dan produk Cartesian. $A$ $B \in$ $A$ $B \cup (A \setminus B) = A$ $A \setminus B$

complexity-theory np-hard np np-intermediate Ari
sumber

Masalah dalam P dapat menjadi NP-complete jika P = NP, yang membuat klaim Anda "mereka tidak bisa keduanya dalam P" salah.

Wojowu

@Wojowu Terima kasih, Anda benar. Saya hanya berasumsi bahwa dipahami bahwa seluruh pertanyaan ini didasarkan pada premis bahwa P! = NP. Kalau tidak, tidak ada artinya / sepele karena kita akan memiliki NPC = P. Saya akan mengedit pertanyaan.

Ari

@Ari, Sebenarnya

, bahkan jika

N P C \neq P

$NPC\not = P$

P = N P

$P=NP$

Tom van der Zanden

@ TomvanderZanden Bagaimana itu mungkin?

jadi jika P = NP maka setiap masalah dalam NP dapat diselesaikan dalam waktu polinomial termasuk masalah dalam NPC.

N P C \subseteq N P

$NPC \subseteq NP$

Ari

@ Arri Set kosong dan set semua string dalam

, tetapi mereka bukan

-complete. Anda tidak dapat mengurangi apa pun menjadi set kosong (atau set semua string) karena selalu menjadi contoh tidak (resp. Ya).

N P

$NP$

N P

$NP$

Tom van der Zanden

Jawaban:

Perpotongan dua bahasa non-NP-hard bisa NP-hard. Contoh: Solusi dari setiap instance 3SAT adalah persimpangan set solusi dari instance HORN-3SAT dan instance ANTIHORN-3SAT. Ini karena klausa 3CNF harus berupa klausa Horn atau anti-Horn dan instance 3SAT adalah gabungan dari klausa tersebut. 3SAT tentu saja NP-lengkap; HORN-3SAT dan ANTIHORN-3SAT keduanya dalam P.

Kyle Jones
sumber

Saya tidak bisa mengikuti teladan Anda. Persimpangan HORN-SAT dan ANTIHORN-SAT adalah bahasa yang cukup membosankan yang pasti ada di P.

Yuval Filmus

HORN-3SAT dapat didefinisikan dengan banyak cara. Salah satu caranya adalah dengan memperbaiki pengkodean instance HORN-3SAT - setiap string mengkodekan beberapa instance semacam itu - dan kemudian HORN-3SAT terdiri dari instance yang memuaskan. Pengkodean ini kemungkinan berbeda dari pengodean yang akan Anda gunakan untuk ANTIHORN-3SAT, jadi tidak jelas apa sebenarnya bahasa persimpangan - pasti bukan SAT.

Yuval Filmus

Kemungkinan lain adalah mendefinisikan HORN-3SAT sebagai bahasa instance 3SAT yang (i) dalam bentuk Horn, (ii) memuaskan. Sekarang persimpangan HORN-3SAT dan ANTIHORN-3SAT masuk akal: itu terdiri dari semua instance 3SAT yang (i) dalam bentuk Horn dan anti-Horn, (ii) memuaskan. Ini hanya bisa lebih mudah daripada masing-masing HORN-3SAT dan ANTIHORN-3SAT.

Yuval Filmus

L_{1}

$L_1$

L_{2}

$L_2$

L_{1} \cap L_{2}

$L_1 \cap L_2$

3 S A T

$\mathsf{3SAT}$

H O R N 3 S A T \cap A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cap\mathsf{ANTIHORN3SAT}$

H O R N 3 S A T \cup A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cup\mathsf{ANTIHORN3SAT}$