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

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.

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 - C N F l + i k - C N F l ,$k$$CNF^l_+$$k$$CNF^l$ .$k, l \geq 3$

(XSAT dla - C N F $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_+$

(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