Czy 1-w-3 SAT pozostaje NP-twardy, nawet jeśli każda zmienna występuje zarówno pozytywnie, jak i negatywnie?

Standardowy problem 1-w-3 SAT (lub XSAT lub X3SAT) to:
Instancja : formuła CNF z każdą klauzulą zawierającą dokładnie 3 literały
Pytanie : czy istnieje zadowalające ustawienie przypisania dokładnie 1 literał na klauzulę prawda?

Problem jest NP-zupełny i pozostaje trudny, nawet jeśli żadna zmienna nie zostanie zanegowana. Zastanawiam się, czy problem ten staje się łatwy, czy trudny, jeśli każda zmienna musi wystąpić przynajmniej raz pozytywnie, a przynajmniej raz negatywnie .

Zwykła redukcja z 3SAT pokazująca, że 1-w-3 SAT jest trudny, zastępuje klauzulę $(x\lor y \lor z)$ według klauzul $(\lnot x \lor a \lor b)$ , $(y\lor b\lor c)$ , $(\lnot z \lor c \lor d)$ gdzie $a,b,c,d$ są świeże dla każdej klauzuli. Tak więc ta redukcja nie pomaga w odpowiedzi na moje pytanie. Miałem problem z wymyśleniem gadżetu wykazującego twardość tego wariantu, ponieważ jeśli dokładnie 1 literał w klauzuli jest prawdziwy, to niesymetryczne 2 literały są fałszywe. Jeśli okaże się to łatwe, myślenie w kategoriach partycji zestawu klauzul może to zrobić, ale nie widzę, jak to zrobić.

cc.complexity-theory np-hardness sat Dominik Peters
źródło

Czy można zmniejszyć do 2 sob.

Joshua Herman

wskazówka: dla każdej var

X_{i}

$X_i$ , dodaj klauzule

(X_{i} \lor {\bar{X}}_{i} \lor W) \land (X_{i} \lor {\bar{X}}_{i} \lor Y) \land (X_{i} \lor {\bar{X}}_{i} \lor Z)

$(X_i\vee \overline X_i \vee W) \wedge (X_i\vee \overline X_i \vee Y)\wedge (X_i\vee \overline X_i \vee Z)$ i powiedzieć,

(W \lor Y \lor \bar{Z})

$(W \vee Y \vee \overline Z)$ .

Neal Young,

Ha, to działa (oczywiście dodając również

(\bar{W} \lor Y \lor Z) \land (W \lor \bar{Y} \lor Z)

$(\overline W \lor Y\lor Z)\land(W\lor\overline Y \lor Z)$ ). Pozostawię pytanie otwarte, na wypadek, gdyby ktokolwiek mógł je rozwiązać bez odrobiny niezadowolenia

X_{i} \lor {\bar{X}}_{i}

$X_i\lor\overline X_i$ sztuczka.

Dominik Peters,

Czy mogę zachęcić cię do napisania pełnej odpowiedzi na własne pytanie, być może opartej na pomyśle Neal Young? (Nawiasem mówiąc, nie jestem pewien, dlaczego to jest „niezadowalające”. Redukcja to redukcja.)

Jeśli ten szczególny przypadek jest tym, na którym naprawdę Ci zależy, to może warto zmodyfikować swoje pytanie, aby odzwierciedlić to dodatkowe ograniczenie?

Odpowiedzi:

W komentarzu OP wyraził zainteresowanie redukcją, która wygenerowała instancje z 3 różnymi zmiennymi na klauzulę. Oto proste podejście:

Redukcja wynika z 1-w-3 SAT z 3 odrębnymi zmiennymi na klauzulę:

Przede wszystkim uwzględnij wszystkie klauzule we wzorze wejściowym jako klauzule we wzorze wyjściowym.
Po drugie, wprowadź trzy nowe zmienne $F_1$ , $F_2$ , i $F_3$ i dodaj następujące trzy klauzule do formuły wyjściowej: $(\neg F_1, F_2, F_3)$ , $(F_1, \neg F_2, F_3)$ , i $(F_1, F_2, \neg F_3)$ .
Wreszcie dla każdej zmiennej $x$ w oryginalnej formule wprowadź nową zmienną $x'$ i dodaj następujące dwie klauzule do formuły wyjściowej: $(x, x', F_1)$ i $(\neg x, \neg x', F_1)$ .

Sprawdźmy, czy ta redukcja robi to, co chcemy. Potrzebujemy następujących właściwości:

Każda klauzula ma zawsze trzy różne zmienne.
Każda zmienna występuje w niektórych klauzulach dodatnio, a w niektórych klauzulach negatywnie.
Formuła wejściowa jest równoważna formule wyjściowej.

Właściwość 1 jest łatwa do sprawdzenia. Łatwo jest również sprawdzić właściwość 2: zmienne $F_1$ , $F_2$ , i $F_3$ każda występuje zarówno pozytywnie, jak i negatywnie w klauzulach dodanych w drugim punkcie wypunktowania, podczas gdy każda inna zmienna we wzorze występuje zarówno pozytywnie, jak i negatywnie w klauzulach dodanych w trzecim punkcie wypunktowania.

Jeśli chodzi o właściwość 3, jest to mniej banalne, ale wciąż łatwe. Możesz łatwo argumentować, że jedynym przypisaniem do zmiennych $F_1$ , $F_2$ , i $F_3$ że spełnienie każdej klauzuli z drugiego punktu jest wykonanie wszystkich trzech $F_i$ s false. Ale wtedy przyjmując wartość false dla $F_1$ , klauzule $(x, x', F_1)$ i $(\neg x, \neg x', F_1)$ dodane w trzecim punkcie są spełnione wtedy i tylko wtedy $x' = \neg x$ . Ponieważ nie ma żadnych innych ograniczeń $x'$ oznacza to, że zawsze możliwe jest rozszerzenie satysfakcjonującego przypisania dla formuły wejściowej na satysfakcjonujące przypisanie dla formuły wyjściowej: po prostu ustaw każdy $x'$ być zaprzeczeniem odpowiedniego $x$ i ustaw każdy $F_i$ do fałszu.

Michaił Rudoy
źródło