Ist 2-SAT mit XOR-Beziehungen NP-vollständig?

Ich frage mich, ob es einen Polynomalgorithmus für "2-SAT mit XOR-Beziehungen" gibt. Sowohl 2-SAT als auch XOR-SAT sind in P, aber ist seine Kombination?

Beispiel Eingabe:

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

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

Mit anderen Worten, die Eingabe ist die folgende boolesche Formel:

Beispielausgabe: Erfüllbar: a = 1, b = 1, c = 0, d = 0.

Sowohl die Anzahl der 2-SAT-Klauseln als auch die Anzahl der XOR-Klauseln in der Eingabe sind , wobei n die Anzahl der booleschen Variablen ist.$O(n)$$n$

2-SAT-mit-XOR-Beziehungen können durch Reduktion von 3-SAT als NP-vollständig nachgewiesen werden. Jede 3-SAT - Klausel in den equisatisfiable 2-SAT-with-XOR-Beziehungen Ausdruck umgeschrieben wird ( x 1 ∨ ¯ y ) ∧ ( y ⊕ x 2 ⊕ z ) ∧ ( ¯ z ∨ x 3 ) mit y und z als neuen Variablen.

Sie haben die Arität Ihrer XOR-Beziehungen nicht angegeben, aber wie bei der üblichen SAT-zu-3SAT-Reduktion können Sie immer festlegen, dass ihre Arität höchstens 3 beträgt. Jetzt sind Sie in einer hervorragenden Position, um Schäfers Dichotomiesatz anzuwenden, der dies tun wird Sagen Sie, ob Ihr Problem in P oder NP-vollständig ist (dies sind die einzigen beiden Optionen). Wenn sich herausstellt, dass es sich um P handelt, könnte der nächste Schritt darin bestehen, Allender et al. Hier erfahren Sie, wie einfach Ihr Problem ist.

Nach Schäfers Dichotomiesatz ist dies NP-vollständig.

$\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$

Wenden Sie nun Schäfers Dichotomiesatz in seiner modernen Form an . Überprüfen Sie jede der sechs Operationen, um festzustellen, ob es sich um einen Polymorphismus handelt:

• $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$. (Consider $(0,1,0)$ and $(1,0,0)$; they satisfy the relation, but $(1,1,0)$ doesn't.)
• Ternary majority: Not a polymorphism of $x \oplus y \oplus z$. (Consider $(0,0,1)$ and $(0,1,0)$ and $(1,0,0)$; they satisfy the relation, but their majority $(0,0,0)$ doesn't.)
• Ternary minority: Not a polymorphism of $x \lor y$. (Consider $(0,1,0)$, $(1,0,0)$, and $(1,1,0)$; they satisfy the relation, but their minority $(0,0,0)$ doesn't.)

It follows that this problem is NP-complete, even if you restrict all the XOR clauses to be of length at most 3.

On the other hand, if all the XOR clauses are restricted to be of length at most 2, then this is in P. In particular $(x \oplus y)$ is equivalent to $(x \lor y) \land (\neg x \lor \neg y)$, so any such formula is equivalent to a 2SAT formula, whose satisfiability can be determined in polynomial time.