Nie wszystkie równe 3-spełnialności

W złożoności obliczeniowej , nie-wszystko równa 3-spełnialności ( NAE3SAT ) jest NP-zupełnym wariantem boolowskiego problemu spełnialności , często używanym w dowodach NP-zupełności.

Definicja

Podobnie jak 3-satisfiability , instancja problemu składa się ze zbioru zmiennych boolowskich i zbioru klauzul, z których każda łączy trzy zmienne lub negacje zmiennych. Jednak w przeciwieństwie do spełnialności 3, która wymaga, aby każda klauzula miała co najmniej jedną prawdziwą wartość logiczną, NAE3SAT wymaga, aby trzy wartości w każdej klauzuli nie były sobie równe (innymi słowy, co najmniej jedna jest prawdziwa, a co najmniej jeden jest fałszywy).

Twardość

NP-zupełność NAE3SAT można udowodnić przez redukcję z 3-spełnialności (3SAT). Najpierw niesymetryczny 3SAT jest redukowany do symetrycznego NAE4SAT przez dodanie wspólnego fikcyjnego literału $klauzuli$ , a następnie NAE4SAT jest redukowany do NAE3SAT przez dzielenie klauzul, jak w przypadku redukcji ogólnego -satisfiability do ${\ displaystyle k}$ 3SOB.

Bardziej szczegółowo, instancja 3SAT ${\ Displaystyle \ Phi = \ bigwedge _ {i = 1} ^ {m} (l_ {i,1} \ vee l_ {i,2} \ vee l_ {i,3})} (gdzie$ l $\ Displaystyle l_ {i, j}}$ są dowolnymi literałami) jest zredukowany do instancji NAE4SAT $, l_ {i, 3}, s)}$${\ Displaystyle \ Psi = \ bigwedge _ {i = 1} ^ {m} (l_ {i, 1}, l_ {i, 2$$gdzie$ jest nową zmienną. Satysfakcjonujące zadanie dla staje się satysfakcjonującym zadaniem dla $Displaystyle$$\ Psi}$ przez ustawienie $\ displaystyle \ Phi$ . I odwrotnie $,$ satysfakcjonujące przypisanie z dla mieć co najmniej jeden inny literał prawdziwy w każdej klauzuli, a zatem być satysfakcjonującym przypisaniem dla $displaystyle$$\ Phi}$ . Wreszcie satysfakcjonujące zadanie z powodu symetrii i $\ displaystyle s = 1}$$\ displaystyle$$Ψ$$\ Psi }$ zostać odwrócony, aby uzyskać satysfakcjonujące zadanie z ${\ displaystyle s = 0}$ .

NAE3SAT pozostaje NP-zupełny, gdy wszystkie klauzule są monotoniczne (co oznacza, że ​​zmienne nigdy nie są negowane), zgodnie z twierdzeniem Schaefera o dychotomii . Monotone NAE3SAT można również interpretować jako przykład problemu podziału zestawu lub jako uogólnienie testowania dwudzielności grafów na 3-jednolite hipergrafy : pyta, czy wierzchołki hipergrafu można pokolorować dwoma kolorami, tak aby żadna hipergraf nie była monochromatyczna. Co więcej, NP-trudno jest znaleźć kolorowanie 3-jednolitych hipergrafów o dowolnej stałej liczbie kolorów, nawet jeśli istnieje 2-kolorowanie.

Łatwe przypadki

W przeciwieństwie do 3SAT, niektóre warianty NAE3SAT, w których grafy reprezentujące strukturę zmiennych i klauzul są grafami planarnymi , można rozwiązać w czasie wielomianowym . W szczególności jest to prawdą, gdy istnieje graf planarny z jednym wierzchołkiem na zmienną, jednym wierzchołkiem na klauzulę, krawędzią dla każdej częstości zmiennej i klauzuli oraz cyklem krawędzi łączących wszystkie wierzchołki zmiennych.