2-Sat con le relazioni XOR sono completi NP?

Question

Mi chiedo se esiste un algoritmo polinomiale per "2-Sat con le relazioni XOR". Sia 2-Sat che Xor-Sat sono in P, ma è la sua combinazione?

Esempio input:

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

• Xor parte: (a xor b xor c xor 1) and (b xor c xor d)

In altre parole, l'input è la seguente formula booleana:

$$ (a lor neg b) land (b lor c) land (b lor d) land (a oplus b oplus neg c) terres . $$

Esempio di output: soddisfacente: a = 1, b = 1, c = 0, d = 0.

Sia il numero di clausole a 2 sacchetti sia il numero di clausole XOR nell'input sono $ o (n) $, dove $ n $ è il numero di variabili booleane.