Ograniczona liczba zmiennych wystąpień w SAT 1-w-3

11

Czy jest znany wynik dotyczący klasy złożoności 1-w-3-SAT z ograniczoną liczbą zmiennych zdarzeń?

Wymyśliłem następującą oszczędną redukcję u Petera Nightingale'a, ale chcę zacytować coś, jeśli jest to znane.

Oto sztuczka, którą wymyśliliśmy. To pokazuje, że 1-w-3-SAT ograniczony do 3 wystąpień na zmienną jest NP kompletny i #P zakończony (ponieważ 1-w-3-SAT jest) , podczas gdy 3-SAT ograniczony do 3 wystąpień jest w P

Powiedzmy, że mamy więcej niż trzy wystąpienia x. Powiedzmy, że potrzebujemy 6. Następnie wprowadzimy 5 nowych zmiennych x2 do x6 równoważnych x oraz dwie nowe zmienne d1 i d2, które mają być fałszywe, z następującymi 6 nowymi klauzulami:

x  -x2 d1
x2 -x3 d1
x3 -x4 d1
x4 -x5 d2
x5 -x6 d2
x6 -x  d2

Oczywiście zastępujemy każde wystąpienie x po pierwszym przez xi dla niektórych i. To daje trzy wystąpienia każdego xi id.

Powyżej ustawia każdą di na fałsz, a wszystkie xi na tę samą wartość. Aby to zobaczyć, x musi być prawdziwe lub fałszywe. Jeśli to prawda, pierwsza klauzula ustawia x2 prawda, a d1 fałsz, a następnie propaguje się w dół klas. Jeśli x jest fałszem, to ostatnia klauzula ustawia x6 fałsz, a d2 fałsz i propaguje klauzule. Jest to oczywiście bardzo oszczędne, więc zachowuje liczenie.

reference-request sat reductions Ian Gent
źródło

12

O ile mi wiadomo, obecne „limity” zostały ustalone w:

Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, Andreas Wotzlaw: XSAT i NAE-SAT z liniowych klas CNF. Discrete Applied Mathematics 167: 1-14 (2014)

Zobacz także tezę Schmidta: Złożoność obliczeniowa SAT, XSAT i NAE-SAT dla liniowych i mieszanych wzorów Horn CNF

Twierdzenie 29 . XSAT pozostaje NP-kompletny dla - i - , $k$ $CNF^l_+$ $k$ $CNF^l$ . $k, l \geq 3$

(XSAT dla - $3$ $CNF^3$ to dokładnie 1-w-3-SAT, gdzie każda zmienna pojawia się dokładnie razy) $l=3$

Zauważ, że twierdzenie to potwierdza również kompletność NP silniejszego przypadku monotonicznego ( ) $CNF_+$

Marzio De Biasi
źródło

C N F_{+}

$CNF_+$

6

(Rozumiem, że to musi być późna odpowiedź; piszę do przyszłych czytelników)

W literaturze jest coraz silniejszy wynik.

Sześcienna pozytywna satysfakcja 1-w-3 została potwierdzona jako NP-zupełna w Moore and Robson, Problemy z płytkami . (Mówią „monotonicznie”, a nie „pozytywnie”. Patrz uwaga dodana w końcu)

Wspomniany wynik jest silniejszy niż wynik w tezie Schmidta, ponieważ tutaj wykres wzoru jest ograniczony do płaskiego. (Warunek jest w rzeczywistości silniejszy: dają one szczególny rodzaj osadzania zwanego osadzaniem prostoliniowym)

$G_B$ $B=(X,C)$ $X\cup C$ $E:= \{ x_iC_j\ :\$ $x_i$ $C_j$ $\}$ $X$ $C$

$B=(X,C)$ $X$ $C$ $X$ $G_B$ $B$
$X$ $C$

Zauważ, że każda klauzula zawiera dokładnie 3 różne zmienne, a każda zmienna pojawia się w dokładnie 3 klauzulach.

Zobacz tezę Tippenhauera na temat Planar 3-SAT i jego wariantów (2016) dla wariantów sat, które ograniczają liczbę zmiennych wystąpień.
Uwaga: istnieje kilka wariantów odkrytych po opublikowaniu tej pracy.

Uwaga dodana: wynik Moore'a i Robsona wykazał, że dodatnia satysfakcja 1-w-3 z Cubic Planar jest NP-zupełna. (To znaczy, formuła boolowska nie jest tylko monotoniczna, jest dodatnia (tj. W ogóle nie ma negowanych literałów)). Niestety w wielu wczesnych artykułach termin „monotoniczny” był używany w znaczeniu „pozytywny”. Redukcja autorstwa Moore'a i Robsona nie wprowadza negowanych literałów. Ich redukcja wynika z Satysfakcji Planar „Monotone” 1-w-3 w pracy Laroche'a Zgodność Planar 1-w-3 jest NP-zupełna . Nie mogłem zdobyć tego artykułu, ale najprawdopodobniej Laroche miał również na myśli pozytywne, mówiąc „monotonnie”. Nawet jeśli nie miał tego na myśli, możemy użyć Satelitarnej Pozytywności 1-w-3 od Mulzera i Rote ' jako problem źródłowy.

Zobacz odpowiedź na pytanie w cs.se

Cyriak Antony
źródło

Ograniczona liczba zmiennych wystąpień w SAT 1-w-3

Odpowiedzi: