MAX-3SAT

MAX-3SAT to problem w poddziedzinie złożoności obliczeniowej informatyki . Uogólnia problem spełnialności Boole'a (SAT), który jest problemem decyzyjnym rozważanym w teorii złożoności . Jest zdefiniowany jako:

Biorąc pod uwagę formułę 3-CNF Φ (tj. z co najwyżej 3 zmiennymi na klauzulę), znajdź przypisanie, które spełnia największą liczbę klauzul.

MAX-3SAT jest kanonicznym kompletnym problemem dla klasy złożoności MAXSNP (pokazany jako kompletny w Papadimitriou str. 314).

Zbliżalność

Wersja decyzyjna MAX-3SAT jest NP-zupełna . Dlatego w czasie wielomianowym można osiągnąć tylko wtedy, gdy P = NP . Przybliżenie w zakresie współczynnika 2 można jednak osiągnąć za pomocą tego prostego algorytmu:

• Wyprowadź rozwiązanie, w którym większość klauzul jest spełniona, gdy wszystkie zmienne = PRAWDA lub wszystkie zmienne = FAŁSZ.
• Każda klauzula jest spełniona przez jedno z dwóch rozwiązań, dlatego jedno rozwiązanie spełnia co najmniej połowę klauzul.

Karloffa -Zwicka działa w czasie wielomianowym i spełnia ≥ 7/8 klauzul. Chociaż ten algorytm jest losowy, można go derandomizować, stosując np. techniki z, aby uzyskać algorytm deterministyczny (w czasie wielomianowym) z tymi samymi gwarancjami przybliżenia.

Twierdzenie 1 (nieprzybliżenie)

twierdzenia PCP wynika, że ​​istnieje ε > 0 takie, że przybliżenie (1- ε ) MAX-3SAT jest NP-trudne .

Dowód:

L ${\ Displaystyle L \ w {\ mathsf {PCP}} (O (\ log (n))$ P. do przez twierdzenie PCP . Dla x ∈ L , formuła 3-CNF Ψ _x jest skonstruowana tak, że

• x ∈ L ⇒ Ψ _x jest spełniony
• x ∉ L ⇒ nie więcej niż (1- ε ) m klauzule Ψ _x są spełnialne.

Weryfikator V odczytuje wszystkie wymagane bity na raz, tj. wykonuje nieadaptacyjne zapytania. Jest to ważne, ponieważ liczba zapytań pozostaje stała.

• Niech q będzie liczbą zapytań.
• Wyliczając wszystkie losowe ciągi R _ja ∈ V , otrzymujemy ciągi poly ( x ), ponieważ długość każdego ciągu ${\ Displaystyle r (x) = O (\ log | x | )}$ .
• Dla każdego R _i
  • V wybiera q pozycje i ₁ ,..., i _q oraz funkcję boolowską f _R : {0,1} ^q ->{0,1} i akceptuje wtedy i tylko wtedy, gdy f _R (π(i ₁ ,...,i _q )). Tutaj π odnosi się do dowodu uzyskanego od Wyroczni.

Następnie próbujemy znaleźć formułę Boole'a , aby to zasymulować. Wprowadzamy zmienne boolowskie x ₁ ,..., x _l , gdzie l jest długością dowodu. Aby wykazać, że weryfikator działa w probabilistycznym czasie wielomianowym , potrzebujemy zgodności między liczbą spełnialnych klauzul a prawdopodobieństwem akceptowanym przez weryfikator.

• Dla każdego R dodaj klauzule reprezentujące f _R ( x _i1 ,..., x _iq ) używając 2 ^{q klauzul} SAT . Klauzule o długości q są konwertowane do długości 3 poprzez dodanie nowych (pomocniczych) zmiennych np. x ₂ ∨ x ₁₀ ∨ x ₁₁ ∨ x ₁₂ = ( x ₂ ∨ x ₁₀ ∨ y _R ) ∧ ( y _R ∨ x ₁₁ ∨ x ₁₂ ). Wymaga to maksymalnie q 2 ^q 3-SAT .
• Jeśli z ∈ L wtedy
  • istnieje dowód π taki, że V ^π ( z ) jest akceptowany dla każdego R _i .
  • Wszystkie klauzule są spełnione, jeśli x _i = π ( i ) i zmienne pomocnicze są dodane poprawnie.
• Jeśli wejście z ∉ L to
  • Dla każdego przypisania do x ₁ ,..., x _l i y _R odpowiedni dowód π( i ) = x _i powoduje, że Weryfikator odrzuca połowę wszystkich R ∈ {0,1} ^{r (| z | )} .
    • Dla każdego R jedna klauzula reprezentująca f _R kończy się niepowodzeniem.
    • Dlatego $_$ _

Można wywnioskować, że jeśli zachodzi to dla każdego problemu NP-zupełnego, to twierdzenie PCP musi być prawdziwe.

Twierdzenie 2

Håstad wykazuje ściślejszy wynik niż Twierdzenie 1, tj. najlepiej znaną wartość ε .

Konstruuje weryfikator PCP dla 3-SAT , który odczytuje tylko 3 bity z dowodu.

Dla każdego ε > 0 istnieje weryfikator PCP M dla 3-SAT , który odczytuje losowy ciąg r o długości ${\ Displaystyle O (\ log (n))}$ i oblicza pozycje zapytania ja _r , j _r , kr _r w dowodzie π i bit b _r . Akceptuje wtedy i tylko wtedy, gdy 'π ( i _r ) ⊕ π ( j _r ) ⊕ π ( k _r ) = b _r .

Weryfikator ma zupełność (1− ε ) i solidność 1/2 + ε (patrz PCP (złożoność) ). Weryfikator spełnia wymagania

${\ Displaystyle z \ w L \ implikuje \ istnieje \ pi Pr [V ^ {\ pi} (x) = 1] \ geq 1-\epsilon }$

${\ Displaystyle Z \ nie \ w L \ implikuje \ forall \ pi Pr [V ^ {\ pi} (x) = 1] \ równoważnik {\ Frac {1} {2}} + \ epsilon}$

Gdyby pierwsze z tych dwóch równań zostało jak zwykle zrównane z „=1”, można by znaleźć dowód π, rozwiązując układ równań liniowych (patrz MAX-3LIN-EQN ) implikujących P = NP .

• Jeśli z ∈ L , spełniony jest ułamek ≥ (1 − ε ) klauzul.
• Jeśli z ∉ L , to dla (1/2 − ε ) ułamka R , 1/4 zdań jest sprzecznych.

To wystarczy, aby udowodnić stopień aproksymacji twardości

${\ Displaystyle {\ Frac {1- {\ Frac {1} {4}} ({\ Frac {1} {2}} - \epsilon )}{1-\epsilon }}={\frac {7}{8}}+\epsilon '}$

Powiązane problemy

MAX-3SAT(B) to ograniczony przypadek specjalny MAX-3SAT , w którym każda zmienna występuje co najwyżej w klauzulach B. Zanim twierdzenie PCP zostało udowodnione, Papadimitriou i Yannakakis wykazali, że dla pewnej ustalonej stałej B problem ten jest MAX SNP-trudny. W konsekwencji, z twierdzeniem PCP, jest również APX-trudne. Jest to przydatne, ponieważ MAX-3SAT(B) może być często używany do uzyskania redukcji zachowującej PTAS w sposób, w jaki MAX-3SAT nie może. Dowody na jawne wartości B obejmują: wszystkie B ≥ 13 i wszystkie B ≥ 3 (co jest najlepsze z możliwych).

Co więcej, chociaż problem decyzyjny 2SAT jest rozwiązywalny w czasie wielomianowym, MAX-2SAT (3) jest również APX-trudny.

Najlepszy możliwy współczynnik przybliżenia dla MAX-3SAT (B), jako funkcja B , wynosi co najmniej ${\ Displaystyle 7/8 + \ Omega (1/B)}$${\ Displaystyle 7/8 + O (1/ {\ sqrt {B}})}$ , chyba że NP = RP . Pewne wyraźne granice stałych aproksymacji dla pewnych wartości B są znane. Berman, Karpinski i Scott udowodnili, że dla „krytycznych” przypadków MAX-3SAT , w których każdy literał występuje dokładnie dwa razy, a każda klauzula ma dokładnie rozmiar 3, problem jest trudny do przybliżenia dla pewnego stałego czynnika.

MAX-EkSAT to sparametryzowana wersja MAX-3SAT , w której każda klauzula ma dokładnie k literałów, dla k ≥ 3. Można to skutecznie przybliżyć współczynnikiem aproksymacji ${\ Displaystyle 1- (1/2) ^{k}}$ przy użyciu pomysłów z teorii kodowania .

Udowodniono, że przypadkowe przypadki współczynnika 8/9 MAX -3SAT można przybliżyć do .

Notatki z wykładów z Uniwersytetu Kalifornijskiego w Berkeley Notatki z teorii kodowania na Uniwersytecie w Buffalo