Complexidade computacional da variante SAT nem todos iguais

Nem todos os SAT iguais são um problema completo do NP. Vamos agora considerar outra variante do problema.

Dado um problema Nem todos iguais (NAESAT) (número arbitrário de literais permitido por cláusula) com uma restrição adicional de que cada par de cláusulas compartilha pelo menos 1 literal (não variáveis, mas literais).

Esse problema ainda é difícil para o NP? Parece que sim, mas não tenho certeza sobre a redução.

Seu problema é difícil de NP , como pode ser visto por uma redução (conhecida, acredito) da CNF-SAT: Reduza de (por exemplo)$3$-SAT da seguinte maneira. Dada uma fórmula$F$, crie uma fórmula para o seu NAE-SAT especial introduzindo exatamente uma variável adicional, digamos $y$. Adicionar$y$ a todas as cláusulas $F$ obter $F'$.

Exemplo: $F = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_2 \vee x_3 \vee \neg x_4)$ torna-se $F' := (x_1 \vee x_2 \vee \neg x_3 \vee y) \wedge (\neg x_2 \vee x_3 \vee \neg x_4 \vee y)$

Depois de fazer isso, todas as cláusulas contêm $y$ e, portanto, compartilha (pelo menos) um literal.

Esboço de prova: se$F$ for satisfatória, use a mesma tarefa satisfatória para satisfazer $F'$, junto com $y = false$.

E se $F'$ é satisfatório, existem duas opções

• $y = false$, nesse caso, a mesma atribuição satisfaz $F$ ($F'$ possui pelo menos um literal literal por cláusula e nunca é $y$, portanto $F$ tem pelo menos um literal verdadeiro por cláusula)
• $y = true$, negue a tarefa satificante de $F'$ satisfazer $F$ (pelo menos um literal literal falso por cláusula em $F'$, depois de negar a atribuição, temos pelo menos um literal verdadeiro por cláusula)