3-SAT gemischt mit 2-SAT-Formeln
Kontext: Bezugnehmend auf die Frage: Komplexität der$(3,2)_s$SAT Problem? und seit dem Artikel von Porshen und Speckenmayer: Erfüllbarkeit gemischter Hornformeln wissen wir das auch wenn$F_3$ ist Horn, das Problem der Entscheidung über die Erfüllbarkeit von $F_3 \wedge F_2$ ist NP-vollständig - wo $F_3$ und $F_2$ sind jeweils 3-CNF- und 2-CNF-Formeln.
Ich frage mich, ob es Fälle gibt, in denen $F_3 \wedge F_2$ist leicht zu entscheiden. Daher meine Frage:
Lassen $F_3$ ein 3-CNF, der nur Klauseln mit genau 3 verschiedenen Literalen enthält und $F_2$ ein 2-CNF, der auf denselben Variablen wie definiert ist $F_3$.
Was ist die Komplexität der Entscheidung über die Erfüllbarkeit von $F_3 \wedge F_2$ wann $F_3$ und $F_2$ sind beide monoton?
Vielen Dank.
Antworten
Wenn $F_3$ und $F_2$ Sind beide monoton, kann die Erfüllbarkeit in Polynomzeit (oder sogar in CoNLOGTIME) überprüft werden $F_3\land F_2$, das ebenfalls monoton ist, ist erfüllbar, wenn es von der $\vec1$ Zuweisung, dh wenn sie die leere Klausel nicht enthält.
Wenn eine der Formeln monoton und die andere monoton negiert sein darf (dh nur negative Literale aufweist), dann ist die Erfüllbarkeit von $F_3\land F_2$ ist NP-vollständig: mit einem 3-CNF $F$ in Variablen $x_1,\dots,x_n$, Lassen $F_3$ sei der monotone 3-CNF aus $F$ durch Ersetzen aller negativen Literale $\neg x_i$ mit neuen Variablen $y_i$, und lass $F_2=\bigwedge_i(\neg x_i\lor\neg y_i)$. Dann$F$ ist mit nicht zufriedenstellend $F_3\land F_2$.
Insbesondere wenn $(\vec x,\vec y)$ ist eine befriedigende Aufgabe für $F_3\land F_2$dann für jeden $i$höchstens einer von $x_i$ oder $y_i$ bekommt Wert $1$, das ist, $y_i\le\neg x_i$. Also, wenn wir die Zuordnung so ändern, dass$y_i:=\neg x_i$wird es noch befriedigen $F_3$wie es monoton ist. Es folgt dem$\vec x$ erfüllt die ursprüngliche Formel $F$.