Est-ce que 2-SAT avec les relations XOR NP-complete?

Question

Je me demande s'il y a un algorithme polynomial pour "2-SAT avec des relations XOR". 2-SAT et XOR-SAT sont en P, mais sa combinaison est-elle?

Exemple d'entrée:

• Pièce de 2 pour 2: (a or !b) and (b or c) and (b or d)

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

En d'autres termes, l'entrée est la formule booléenne suivante:

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

Exemple de sortie: satisfaisant: a = 1, b = 1, c = 0, d = 0.

Le nombre de clauses 2-SAT et le nombre de clauses XOR dans l'entrée sont $ o (n) $, où $ n $ est le nombre de variables booléennes.