3-SAT misturado com fórmulas 2-SAT
Contexto: Referindo-se à questão: Complexidade do$(3,2)_s$SAT problem? e desde o artigo de Porshen e Speckenmayer: Satisfiability of Mixed Horn formulas , sabemos que mesmo quando$F_3$ é Horn, o problema de decidir a satisfatibilidade de $F_3 \wedge F_2$ é NP-completo - onde $F_3$ e $F_2$ são, respectivamente, fórmulas 3-CNF e 2-CNF.
Estou me perguntando se existem alguns casos onde $F_3 \wedge F_2$é fácil decidir. Daí a minha pergunta:
Deixei $F_3$ um 3-CNF contendo apenas cláusulas com exatamente 3 literais diferentes e $F_2$ um 2-CNF definido nas mesmas variáveis que $F_3$.
Qual é a complexidade de decidir a satisfatibilidade de $F_3 \wedge F_2$ quando $F_3$ e $F_2$ são ambos monótonos?
Obrigado.
Respostas
E se $F_3$ e $F_2$ são monótonos, a satisfatibilidade pode ser verificada em tempo polinomial (ou mesmo em CONLOGTIME), como $F_3\land F_2$, que também é monótono, é satisfatório se for satisfeito pelo $\vec1$ atribuição, isto é, se não contiver a cláusula vazia.
Se uma das fórmulas puder ser monótona e a outra negar monótona (ou seja, tendo apenas literais negativos), então a satisfatibilidade de $F_3\land F_2$ é NP-completo: dado um 3-CNF $F$ em variáveis $x_1,\dots,x_n$, deixei $F_3$ ser o monótono 3-CNF obtido de $F$ substituindo todos os literais negativos $\neg x_i$ com novas variáveis $y_i$, e deixar $F_2=\bigwedge_i(\neg x_i\lor\neg y_i)$. Então$F$ é insatisfatório com $F_3\land F_2$.
Em particular, se $(\vec x,\vec y)$ é uma tarefa satisfatória para $F_3\land F_2$, então para cada $i$, no máximo um de $x_i$ ou $y_i$ obtém valor $1$, isso é, $y_i\le\neg x_i$. Assim, se modificarmos a atribuição para que$y_i:=\neg x_i$, ainda vai satisfazer $F_3$porque é monótono. Segue que$\vec x$ satisfaz a fórmula original $F$.