MAXEkSAT

MAXEkSAT to problem w teorii złożoności obliczeniowej , który jest maksymalizacyjną wersją problemu spełnialności Boole'a 3SAT . W MAXEkSAT każda klauzula ma dokładnie k literałów, każdy z różnymi zmiennymi i jest w koniunkcyjnej postaci normalnej . Są to tak zwane formuły k-CNF. Problem polega na określeniu maksymalnej liczby klauzul, które mogą być spełnione przez przypisanie prawdy do zmiennych w klauzulach.

Mówimy, że algorytm A zapewnia przybliżenie α do MAXEkSAT, jeśli dla pewnego ustalonego dodatniego α mniejszego lub równego 1 i dla każdego wzoru kCNF φ , A może znaleźć prawdziwość przypisania zmiennych φ , które spełnią co najmniej α -ułamek maksymalnej liczby klauzul spełnialnych φ .

Ponieważ problem NP-trudny k -SAT (dla k ≥ 3) jest równoważny z ustaleniem, czy odpowiadająca mu instancja MAXEkSAT ma wartość równą liczbie klauzul, MAXEkSAT również musi być NP-trudny, co oznacza, że nie istnieje algorytm czasu wielomianowego chyba że P=NP . Naturalnym następnym pytaniem jest zatem znalezienie przybliżonych rozwiązań: jaka jest największa liczba rzeczywista α < 1 taka, że jakiś jawny algorytm P (złożoność) zawsze znajduje rozwiązanie o rozmiarze α·OPT , gdzie OPT to (potencjalnie trudne do znalezienia) zadanie maksymalizujące. Chociaż algorytm jest wydajny, nie jest oczywiste, jak usunąć jego zależność od losowości. Istnieją problemy związane ze spełnialnością koniunkcyjnych formuł boolowskich w postaci normalnej.

Algorytm aproksymacji

Istnieje prosty $losowy$ który MAXEkSAT: niezależnie ustaw każdą zmienną na true z prawdopodobieństwem 1 / 2 , w przeciwnym razie ustaw na false.

Każda dana klauzula c jest niespełniona tylko wtedy, gdy wszystkie jej k literały składowe mają wartość false. Ponieważ każdy literał w klauzuli ma 1 ⁄ 2 szans na ocenę prawdy niezależnie od jakiejkolwiek wartości logicznej któregokolwiek z pozostałych literałów, prawdopodobieństwo, że wszystkie są fałszywe, wynosi ${\ Displaystyle \textstyle ({\frac {1}{2}})^{k}={\frac {1}{2^{k}}}}$ . Zatem prawdopodobieństwo, że c jest rzeczywiście spełnione, wynosi ${\ Displaystyle \ textstyle 1- {\ Frac {1} {2 ^ {k}}}}$ , więc zmienna wskaźnikowa ${\ Displaystyle \ textstyle 1_ {c}}$ (czyli 1, jeśli c jest prawda i 0 w przeciwnym razie) ma oczekiwanie ${\ Displaystyle \ textstyle 1- {\ Frac {1} {2 ^ {k}}}}$ . Suma wszystkich zmiennych wskaźnikowych po wszystkich ${\ Displaystyle \ textstyle | C |} to$ klauzule $)$ za ${\ Displaystyle \$ \ lewo część klauzul w oczekiwaniu. Ponieważ optymalne rozwiązanie nie może zadowolić więcej niż wszystkich ${\ displaystyle \ textstyle | C|}$ klauzul, mamy to ${\ Displaystyle {\ textit {ALG}} = \ lewo (1- {\ Frac {1} {2 ^ {k}}} \ prawej) \ cdot | C |> \ left (1- {\ Frac {1}{2^ {k}}} \ right) \ cdot {\ textit {OPT}}} , więc algorytm$ znajduje za ${\ Displaystyle \ textstyle \geq \left(1-{\frac {1}{2^{k}}}\right)}$ przybliżenie do prawdziwie optymalnego rozwiązania w oczekiwaniu.

Pomimo wysokich oczekiwań, ten algorytm może czasami natknąć się na rozwiązania o wartości niższej niż oczekiwana, którą obliczyliśmy powyżej. Jednak w dużej liczbie prób średni ułamek spełnionych klauzul będzie miał tendencję do ${\ Displaystyle \ textstyle \ lewo (1- {\ Frac {1} {2 ^ {k}}} \ prawo)}$ . Oznacza to dwie rzeczy:

$_$ istnieć przypisanie Gdyby tak nie było, nigdy nie moglibyśmy osiągnąć tak dużej średniej wartości w dużej liczbie prób.
Jeśli uruchomimy algorytm wiele razy, co najmniej połowa prób (w oczekiwaniu) spełni pewne ${\ Displaystyle \ textstyle (1- {\ Frac {2} {2 ^ {k }}})}$ część klauzul. Dzieje się tak, ponieważ jakikolwiek mniejszy ułamek obniżyłby średnią na tyle, że algorytm musi czasami spełniać więcej niż 100% klauzul, aby wrócić do swoich oczekiwań ( $\ Displaystyle \ textstyle \ lewo (1- { \frac {2}{2^{k}}}\right)}$ , co nie może się zdarzyć. Rozszerzając to za pomocą nierówności Markowa , przynajmniej niektóre ${\ Displaystyle \ textstyle 1- \ lewo ({\ Frac {1} {1 + 2 ^ {k} \ epsilon}} \ prawej) }$ -ułamek prób (w oczekiwaniu) spełni co najmniej za ${\ Displaystyle \ textstyle \ lewo (1 - {\ Frac {1} {2 ^ {k}}} - \ epsilon \right)}$ -ułamek klauzul. Dlatego dla dowolnego dodatniego ${\ Displaystyle \ textstyle \ epsilon}$ , potrzeba tylko wielomianowej liczby losowych prób, aż spodziewamy się znaleźć zadanie spełniające co najmniej za ${\ Displaystyle \ textstyle \ lewo (1- {\ frac {1}{2^{k}}}-\epsilon \right)}$ część klauzul.

Bardziej solidna analiza (taka jak w ) pokazuje, że w rzeczywistości spełnimy co najmniej za ${\ Displaystyle \ textstyle \ lewo (1- {\ Frac {1} {2 ^ {k }}} \ prawej)} -$ ułamek klauzul stały ułamek czasu (zależny tylko od k ), bez utraty ${\ displaystyle \ textstyle \ epsilon}$ .

Derandomizacja

Chociaż powyższy algorytm jest wydajny, nie jest oczywiste, jak usunąć jego zależność od losowości. Wypróbowanie wszystkich możliwych losowych przypisań jest równoznaczne z naiwnym podejściem brutalnej siły, więc może zająć wykładniczy czas. Sprytny sposób derandomizacji powyższego w czasie wielomianowym polega na pracy nad kodami korygującymi błędy , spełniającymi za ${\ Displaystyle \ textstyle \ lewo (1 - {\ Frac {1} {2 ^ {k}} }\right)}$ ułamek klauzul w wielomianie czasowym w wielkości wejściowej (chociaż wykładnik zależy od k ).

Aby znaleźć algorytm, potrzebujemy jednej definicji i dwóch faktów.

Definicja

${\ Displaystyle S \ subseteq \ {0,1 \} ^ {n}}$ jest niezależnym źródłem $ℓ$ -mądrym, jeśli dla równomiernie wybranego losowego $(x 1, x 2, ..., x n) \in S,$ $x 1, x 2, ..., x n$ są $ℓ$ niezależnymi zmiennymi losowymi.

Fakt 1

Zauważ, że takie przypisanie można znaleźć wśród elementów dowolnego $niezależnego$ źródła na n zmiennych binarnych . Łatwiej to zauważyć, gdy zdasz sobie sprawę, że $ℓ$ jest tak naprawdę dowolnym zbiorem wektorów binarnych na ${0, 1} n$ z tą właściwością, że wszystkie ograniczenia tych wektorów do $ℓ$ współrzędnych muszą przedstawiać 2 ^ℓ możliwe kombinacje binarne taką samą liczbę razy.

Fakt 2

Przypomnijmy, że BCH _{2, m , re} jest za ${\ Displaystyle [n = 2 ^ {m}, n-1-\ lceil {d-2}/2\rceil m,d]_{2}}$ kod liniowy.

Istnieje $ℓ -$ $źródło o mądre, ℓ Kod +1$ niezależne $2$ a , który jest kodem liniowym. Ponieważ każdy kod BCH można przedstawić jako obliczalne w czasie wielomianowym ograniczenie powiązanego kodu Reeda Solomona , który sam w sobie jest silnie jawny, istnieje algorytm czasu wielomianowego do znajdowania takiego przypisania do x _ja . Dowód faktu 2 można znaleźć w Dual of BCH jest niezależnym źródłem .

Zarys algorytmu

Algorytm działa na zasadzie generowania $BCH 2,log n, ℓ +1$ , obliczania jego dualności (która jako zbiór jest niezależnym źródłem $ℓ$ ) i traktowania każdego elementu (słowa kodowego) tego źródła jako przyporządkowania prawdy do n zmiennych w φ . Przynajmniej jeden z nich będzie spełniał co najmniej $1 - 2 - ℓ$ klauzul φ , ilekroć φ jest w postaci kCNF, $k = ℓ$ .

Powiązane problemy

Istnieje wiele problemów związanych ze spełnialnością koniunkcyjnych formuł boolowskich w postaci normalnej.

Problemy decyzyjne :
- 2SOB
- 3SOB
Problemy optymalizacyjne, gdzie celem jest maksymalizacja liczby spełnionych klauzul:
- MAX-SAT i odpowiadająca mu ważona wersja Weighted MAX-SAT
- MAX- k SAT, gdzie każda klauzula ma dokładnie k zmiennych:
  - MAX-2SAT
  - MAX-3SAT
  - MAXEkSAT
- Problem częściowej maksymalnej spełnialności (PMAX-SAT) pyta o maksymalną liczbę klauzul, które mogą być spełnione przez dowolne przypisanie danego podzbioru klauzul. Pozostałe warunki muszą być spełnione.
- Problem miękkiej spełnialności (soft-SAT), biorąc pod uwagę zestaw problemów SAT, prosi o maksymalną liczbę zestawów, które mogą być spełnione przez dowolne zadanie.
- Minimalny problem spełnialności.
Problem MAX-SAT można rozszerzyć do przypadku, gdy zmienne problemu spełnienia ograniczeń należą do zbioru liczb rzeczywistych. Problem sprowadza się do znalezienia najmniejszego q takiego, że q - rozluźnione przecięcie więzów nie jest puste.

Zobacz też

Linki zewnętrzne

Notatki z teorii kodowania w MIT