3-SAT miscelato con formule 2-SAT
Contesto: in riferimento alla domanda: complessità del$(3,2)_s$Problema SAT? e poiché l'articolo di Porshen e Speckenmayer: Satisfiability of mixed Horn formas , sappiamo che anche quando$F_3$ è Horn, il problema di decidere la soddisfacibilità di $F_3 \wedge F_2$ è NP-completo - dove $F_3$ e $F_2$ sono rispettivamente formule 3-CNF e 2-CNF.
Mi chiedo se esistono casi in cui $F_3 \wedge F_2$è facile decidere. Da qui la mia domanda:
Permettere $F_3$ un 3-CNF contenente solo clausole con esattamente 3 letterali differenti e $F_2$ un 2-CNF definito sulle stesse variabili di $F_3$.
Qual è la complessità di decidere la soddisfacibilità di $F_3 \wedge F_2$ quando $F_3$ e $F_2$ sono entrambi monotoni?
Grazie.
Risposte
Se $F_3$ e $F_2$ sono entrambi monotoni, la soddisfacibilità può essere verificata in tempo polinomiale (o anche in coNLOGTIME), come $F_3\land F_2$, anch'esso monotono, è soddisfacente se e solo se è soddisfatto dal $\vec1$ assegnazione, cioè se e solo se non contiene la clausola vuota.
Se una delle formule può essere monotona e l'altra nega monotona (cioè, avendo solo letterali negativi), allora la soddisfacibilità di $F_3\land F_2$ è NP-completo: dato un 3-CNF $F$ in variabili $x_1,\dots,x_n$, permettere $F_3$ essere il monotono 3-CNF ottenuto da $F$ sostituendo tutti i letterali negativi $\neg x_i$ con nuove variabili $y_i$, e lascia $F_2=\bigwedge_i(\neg x_i\lor\neg y_i)$. Poi$F$ è equisoddisfacente con $F_3\land F_2$.
In particolare, se $(\vec x,\vec y)$ è un compito soddisfacente per $F_3\land F_2$, quindi per ciascuno $i$, al massimo uno di $x_i$ o $y_i$ ottiene valore $1$, questo è, $y_i\le\neg x_i$. Quindi, se modifichiamo l'assegnazione in modo che$y_i:=\neg x_i$, soddisferà comunque $F_3$in quanto è monotono. Ne consegue che$\vec x$ soddisfa la formula originale $F$.