O 2-SAT com relações XOR NP está completo?

Gostaria de saber se existe um algoritmo polinomial para "2-SAT com relações XOR". O 2-SAT e o XOR-SAT estão em P, mas é sua combinação?

Exemplo de entrada:

• Parte 2-SAT: (a or !b) and (b or c) and (b or d)

• Parte XOR: (a xor b xor c xor 1) and (b xor c xor d)

Em outras palavras, a entrada é a seguinte fórmula booleana:

Saída de exemplo: Satisfazível: a = 1, b = 1, c = 0, d = 0.

O número de cláusulas 2-SAT e o número de cláusulas XOR na entrada são , onde n é o número de variáveis ​​booleanas.$O(n)$$n$

As relações 2-SAT com XOR podem ser comprovadas como NP-completas através da redução de 3-SAT. Qualquer cláusula 3-SAT pode ser reescrita para o equisatisfiable 2-SAT-com-XOR-relações expressão ( x 1 ∨ ¯ y ) ∧ ( y ⊕ x 2 ⊕ z ) ∧ ( ¯ z ∨ x 3 ) com y e z como novas variáveis.

Você não especificou a aridade de suas relações XOR, mas, como na redução usual de SAT para 3SAT, sempre é possível organizar a aridade deles no máximo 3. Agora você está em ótima posição para aplicar o teorema da dicotomia de Schaefer , que informe se o seu problema está em P ou NP-complete (estas são as duas únicas opções). Se estiver em P, o próximo passo pode ser observar Allender et al. , que permitirá que você saiba como é fácil o seu problema.

Pelo teorema da dicotomia de Schaefer , isso é NP-completo.

$\Gamma$$R(x,y,z)$$x \lor y$$x \lor \neg y$$\neg x \lor \neg y$$x \oplus y \oplus z$$x \oplus y \oplus \neg z$

Agora aplique o teorema da dicotomia de Schaefer, em sua forma moderna . Verifique cada uma das seis operações para ver se elas são um polimorfismo:

• $x \lor y$
• $\neg x \lor \neg y$
• $x \lor y$$(0,1,0)$$(1,0,0)$$(0,0,0)$
• $\neg x \lor \neg y$$(0,1,0)$$(1,0,0)$$(1,1,0)$
• $x \oplus y \oplus z$$(0,0,1)$$(0,1,0)$$(1,0,0)$$(0,0,0)$
• $x \lor y$$(0,1,0)$$(1,0,0)$$(1,1,0)$$(0,0,0)$

Daqui resulta que esse problema é NP-completo, mesmo que você restrinja todas as cláusulas XOR a um comprimento máximo de 3.

$(x \oplus y)$$(x \lor y) \land (\neg x \lor \neg y)$