Apakah 1-in-3 SAT tetap NP-keras bahkan jika setiap variabel terjadi positif dan negatif?

Masalah standar 1-in-3 SAT (atau XSAT atau X3SAT) adalah:
Instance : rumus CNF dengan setiap klausa yang mengandung tepat 3 liter
Pertanyaan : apakah ada pengaturan penugasan yang memuaskan tepatnya 1 liter per klausa benar?

Masalahnya adalah NP-lengkap dan tetap sulit bahkan jika tidak ada variabel yang dinegasikan. Saya bertanya-tanya apakah masalah ini menjadi mudah atau tetap sulit jika setiap variabel diharuskan untuk muncul setidaknya satu kali secara positif dan setidaknya satu kali secara negatif .

Pengurangan biasa dari 3SAT menunjukkan bahwa 1-in-3 SAT sulit menggantikan klausa dengan klausa , , mana $(x\lor y \lor z)$ $(\lnot x \lor a \lor b)$ $(y\lor b\lor c)$ $(\lnot z \lor c \lor d)$ $a,b,c,d$ segar untuk setiap klausa. Dengan demikian, pengurangan ini tidak membantu dalam menjawab pertanyaan saya. Saya mengalami masalah dengan gadget yang menunjukkan kekerasan varian ini, karena jika tepat 1 literal dalam klausa benar, maka 2 liter yang non-simetris adalah salah. Jika ternyata mudah, berpikir dalam hal partisi set klausa mungkin bisa melakukannya, tetapi saya tidak bisa melihat caranya.

cc.complexity-theory np-hardness sat Dominik Peters
sumber

Bisakah dikurangi menjadi 2 sat?

Joshua Herman

X_{i}

$X_i$

(X_{i} \lor {\bar{X}}_{i} \lor W) \land (X_{i} \lor {\bar{X}}_{i} \lor Y) \land (X_{i} \lor {\bar{X}}_{i} \lor Z)

$(X_i\vee \overline X_i \vee W) \wedge (X_i\vee \overline X_i \vee Y)\wedge (X_i\vee \overline X_i \vee Z)$

(W \lor Y \lor \bar{Z})

$(W \vee Y \vee \overline Z)$

(\bar{W} \lor Y \lor Z) \land (W \lor \bar{Y} \lor Z)

$(\overline W \lor Y\lor Z)\land(W\lor\overline Y \lor Z)$

X_{i} \lor {\bar{X}}_{i}

$X_i\lor\overline X_i$

Bolehkah saya mendorong Anda untuk menulis jawaban lengkap untuk pertanyaan Anda sendiri, mungkin berdasarkan ide Neal young? (Kebetulan, saya tidak yakin mengapa itu "tidak memuaskan". Pengurangan adalah pengurangan.)

Jika kasus khusus itu adalah yang benar-benar Anda pedulikan, maka mungkin masuk akal untuk mengedit pertanyaan Anda untuk mencerminkan kendala ekstra itu?

Dalam komentar, OP menyatakan minatnya pada pengurangan yang menghasilkan contoh dengan 3 variabel berbeda per klausa. Inilah pendekatan sederhana:

Pengurangannya dari 1-in-3 SAT dengan 3 variabel berbeda per klausa:

Pertama-tama, sertakan semua klausa dalam formula input sebagai klausa dalam formula output.
$F_1$ $F_2$ $F_3$ $(\neg F_1, F_2, F_3)$ $(F_1, \neg F_2, F_3)$ $(F_1, F_2, \neg F_3)$
$x$ $x'$ $(x, x', F_1)$ $(\neg x, \neg x', F_1)$

Mari kita verifikasi bahwa pengurangan ini melakukan apa yang kita inginkan. Properti berikut adalah yang kami inginkan:

Setiap klausa selalu memiliki tiga variabel berbeda.
Setiap variabel terjadi dalam beberapa klausa secara positif dan dalam beberapa klausa negatif.
Rumus input setara dengan rumus output.

$F_1$ $F_2$ $F_3$

$F_1$ $F_2$ $F_3$ $F_i$ $F_1$ $(x, x', F_1)$ $(\neg x, \neg x', F_1)$ $x' = \neg x$ $x'$ $x'$ $x$ $F_i$

Mikhail Rudoy
sumber

Apakah 1-in-3 SAT tetap NP-keras bahkan jika setiap variabel terjadi positif dan negatif?

Jawaban: