varian dari Critical SAT

Bahasa Critical SAT didefinisikan sebagai himpunan rumus boolean sedemikian rupa sehingga tetapi menghapus klausa apa pun dari membuatnya memuaskan. Diketahui bahwa SAT kritis adalah lengkap. Saya bertanya-tanya tentang varian berikut: diberi rumus , apakah ini kasus bahwa ada di dan bahwa ada beberapa klausa sehingga (alih-alih untuk semua klausa, ada klausa) . Apakah varian lengkap?f f ∈ U N S A T f D P C N F f f U N S A T c f ∖ c ∈ S A T D $CNF$$f$$f \in UNSAT$$f$$DP$$CNF$$f$$f$$UNSAT$$c$$f \setminus c \in SAT$$DP$

Jelas bahwa bahasa Anda dalam DP. Untuk menunjukkan bahwa ini adalah DP-hard, kami akan memberikan pengurangan dari SAT-UNSAT ke bahasa Anda, yang dapat kami sebut CRIT-UNSAT. Mengingat sepasang CNFs , biarkan x , y menjadi variabel segar, dan biarkan h = ( f ∨ ¬ x ) ∧ ( g ∨ x ) ∧ ( g ∨ y ) ∧ ¬ x ∧ ( x ∨ ¬ y ) . Di sini f $(f,g)$$x,y$

Misalkan pertama bahwa adalah memuaskan dan g tidak memuaskan. Karena g tidak memuaskan, h tidak memuaskan. Karena f adalah satisfiable, h ∖ ¬ x adalah satisfiable. Jadi h ada di CRIT-SAT.$f$$g$$g$$h$$f$$h \setminus \lnot x$$h$

Sebaliknya, anggaplah ada di CRIT-SAT. Karena h tidak memuaskan, g tidak memuaskan. Untuk beberapa klausa c , h ∖ c memuaskan. Jika c ∈ f ∨ ¬ x maka jelas h ∖ c masih kurang memuaskan. Demikian pula, jika c ∈ g ∨ x maka h ∖ c masih tidak memuaskan, karena g ∨ y . Jika c ∈ g ∨ y atau c $h$$h$$g$$c$$h \setminus c$$c \in f \lor \lnot x$$h \setminus c$$c \in g \lor x$$h \setminus c$$g \lor y$$c \in g \lor y$ maka h ∖ c masih tidak memuaskan, karena g ∨ x . Jadi c = ¬ x , yang berarti bahwa h | x = 1 memuaskan, yaitu, f memuaskan.$c = x \lor \lnot y$$h \setminus c$$g \lor x$$c = \lnot x$$h|_{x=1}$$f$