Czy 2-SAT z relacjami XOR NP-jest kompletny?

11

Zastanawiam się, czy istnieje algorytm wielomianowy dla „2-SAT z relacjami XOR”. Zarówno 2-SAT, jak i XOR-SAT są w P, ale czy jest to kombinacja?

Przykładowe dane wejściowe:

Część 2-SAT: (a or !b) and (b or c) and (b or d)
Część XOR: (a xor b xor c xor 1) and (b xor c xor d)

Innymi słowy, wejściem jest następująca formuła boolowska:

(za \lor \neg b) \land (b \lor do) \land (b \lor re) \land (za \oplus b \oplus \neg do) \land (b \oplus do \oplus re) .

$(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).$

Przykładowy wynik: Zadowalający: a = 1, b = 1, c = 0, d = 0.

Zarówno liczba klauzul 2-SAT, jak i liczba klauzul XOR na wejściu to , gdzie jest liczbą zmiennych boolowskich. $O(n)$ $n$

— Albert Hendriks
źródło

1

ten problem jest dość blisko, xor bitowy wektorów równy wektorowi docelowemu , cstheory.se

— vzn

11

Relacje 2-SAT-z-XOR można udowodnić jako NP-zupełne poprzez redukcję z 3-SAT. Dowolną klauzulę 3-SAT można przepisać w wyrażeniu relacji 2-SAT-z-XOR nie do spełnienia z i jako nowe zmienne.

(x_{1} \lor x_{2)} \lor x_{3)})

$(x_1 \lor x_2 \lor x_3)$

(x_{1} \lor \bar{y}) \land (y \oplus x_{2)} \oplus z) \land (\bar{z} \lor x_{3)})

$(x_1 \lor \overline{y}) \land (y \oplus x_2 \oplus z) \land (\overline{z} \lor x_3)$

y

$y$

z

$z$

— Kyle Jones
źródło

Wszystkie odpowiedzi wydają się poprawne lub pomocne, ale uważam, że ta jest najbardziej elegancka (imho).

— Albert Hendriks

1

Niezła odpowiedź. Warto wspomnieć, że sama równoważność nie byłaby tutaj wystarczająca (ponieważ zadowalające przypisania wyrażeń odpowiadających wszystkim klauzulom zadowalającej CNF mogą się nie zgadzać), ale twoje przepisane wyrażenie faktycznie ma odpowiadające zadowalające przypisanie dla każdego spełniającego przypisania oryginalna klauzula.

— Klaus Draeger

7

Nie określiłeś arsencji swoich relacji XOR, ale tak jak w zwykłej redukcji SAT-do-3SAT, zawsze możesz ustalić, że ich arsenacja będzie wynosić co najwyżej 3. Teraz jesteś w dobrej sytuacji, aby zastosować twierdzenie dychotomii Schaefera , które będzie powiedzą ci, czy twój problem jest w P czy NP-complete (są to tylko dwie opcje). Jeśli okaże się, że jest to P, następnym krokiem może być Allender i in. , dzięki czemu dowiesz się, jak łatwy jest twój problem.

— Yuval Filmus
źródło

O (n)

$O(n)$

5

Według twierdzenia dychotomii Schaefera jest to NP-zupełne.

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

Teraz zastosuj twierdzenie dychotomii Schaefera w jego nowoczesnej formie . Sprawdź każdą z sześciu operacji, aby sprawdzić, czy jest to polimorfizm:

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

Wynika z tego, że ten problem jest NP-zupełny, nawet jeśli ograniczysz wszystkie klauzule XOR do maksymalnej długości 3.

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

— DW
źródło