Varian dari SAT kritis di DP

Bahasa $L$ ada di kelas $DP$ jika ada dua bahasa $L1 \in NP$ dan $L2 \in coNP$ sehingga $L = L1 \cap L2$

Sebuah kanonik $DP$ masalah -Lengkap adalah SAT-UNSAT: diberikan dua ekspresi 3-CNF, $F$ dan $G$ , apakah benar bahwa $F$ adalah satisfiable dan $G$ tidak?

Kritis SAT masalah juga dikenal $DP$ -Lengkap: Mengingat ekspresi 3-CNF $F$ , apakah benar bahwa $F$ adalah unsatisfiable tapi menghapus klausul setiap membuat satisfiable?

Saya sedang mempertimbangkan varian berikut dari masalah SAT Kritis: Diberikan ekspresi 3-CNF $F$ , apakah benar $F$ memuaskan tetapi menambahkan klausa 3 (dari $F$ tetapi menggunakan variabel yang sama dengan $F$ ) membuatnya tidak memuaskan? Tetapi saya tidak berhasil menemukan pengurangan dari SAT-UNSAT atau bahkan membuktikan itu adalah $NP$ atau $coNP$ hard.

Pertanyaan saya: apakah varian ini DP-lengkap?

Terima kasih atas jawaban anda

[Aku membuatnya menjadi jawaban yang tepat tapi seseorang memberikannya -1]

Jika ada klausa yang diizinkan untuk ditambahkan, maka bahasa tersebut kosong - jelas untuk setiap rumus memuaskan Anda dapat menambahkan 3 klausa c yang terdiri dari variabel yang tidak muncul dalam F : F ∪ { c } akan memuaskan.$F$$c$$F$$F \cup \{ c \}$

Jika klausa yang ditambahkan harus menggunakan variabel , maka bahasa tersebut dalam P.$F$

Pembenaran adalah sebagai berikut:

Mengambil , yaitu F ∈ S A T dan untuk setiap 3-klausul c pada variabel F , F ∪ { c } ∈ U N S A T . Katakan c = l 1 ∨ l 2 ∨ l 3 ∉ F , di mana l i adalah literal. Karena F ∪ { c } adalah UNSAT, semua model F harus memiliki l $F \in L$$F \in SAT$$c$$F$$F \cup \{c\} \in UNSAT$$c = l_1 \lor l_2 \lor l_3 \notin F$$l_i$$F \cup \{ c \}$$F$ (untuk i = 1 , 2 , 3 ) - karena jika beberapa model memiliki misalnya l 1 = 1 , maka itu akan memenuhi c dan F ∪ { c } . Sekarang, asumsikan ada klausa lain c ′ yang persis seperti c , tetapi dengan satu atau lebih literal terbalik dan sedemikian sehingga c ′ ∉ F , katakanlah c ′ = ¬ l 1 ∨ l 2 ∨ l $l_i=0$$i=1,2,3$$l_1=1$$c$$F \cup \{c\}$$c'$$c$$c' \notin F$$c' = \neg l_1 \lor l_2 \lor l_3$. Maka dengan argumen yang sama semua model harus memiliki l 1 = 1 . Dengan demikian, kondisi yang diperlukan untuk F ∈ L adalah bahwa untuk setiap klausul c ∈ F ada tepat 6 klausul lainnya di F yang menggunakan tiga variabel c - memungkinkan panggilan subset 7-klausul tersebut F blok . Perhatikan bahwa setiap blok menyiratkan tugas memuaskan unik untuk variabel-variabelnya. Ketika kondisi yang diperlukan ini terpenuhi, F bisa secara unik memuaskan atau tidak memuaskan. Dua kasus dapat dibedakan dengan menguji apakah penugasan tersirat oleh blok $F$$l_1 = 1$$F \in L$$c \in F$$F$$c$$F$ $F$$F$ bentrokan, yang jelas dapat dilakukan dalam waktu linier.

Bolehkah saya mengajukan jawaban atas pertanyaan saya sendiri berkat komentar Anda: varian Critical SAT ada di P.

$F$$F$$F$

$F$$F$

$F$

$F$$F$$F$$F$$F$$F$

$F$$F$$F$$F$$F$$F$$F$$F$$F$

$F$$F$

$F$$\binom{n}{3}$$\frac{n(n-1)(n-2)}{3}$$n$