Algorytmy aproksymacji super wielomianu dla MAX 3SAT

20

Stany PCP twierdzenie, że nie ma czasu na wielomian algorytm MAX 3SAT znaleźć spełniającą zadanie klauzule spe wzorze 3SAT chyba P = N P .7/8+ϵP=NP

Nie jest to prosta wielomian algorytm czasu, który spełnia klauzul. Tak, możemy to zrobić lepiej niż 7 / 8 + ε jeśli pozwolimy algorytmy super wielomianu? Jakie współczynniki aproksymacji możemy osiągnąć za pomocą quasi-wielomianowych algorytmów czasu ( n O ( log n ) ) lub za pomocą sub wykładniczych algorytmów czasu ( 2 o ( n ) )? Szukam odniesień do takich algorytmów.7/87/8+ϵnO(logn)2o(n)

Mohammad Al-Turkistany
źródło

Odpowiedzi:

29

Można dostać przybliżenie dla MAX3SAT że przebiega w 2 O ( ε n ) czas bez większych kłopotów. Oto pomysł. Podziel zbiór zmiennych na O ( 1 / ε ) grupy ε n zmiennych każda. Dla każdej grupy wypróbuj wszystkie 2 ε n sposoby przypisywania zmiennych w grupie. Dla każdego ze zmniejszoną ilością uruchom Karloff i Zwick 7 / 8 -approximation. Wyprowadź zadanie spełniające maksymalną liczbę klauzul, spośród wszystkich tych prób.7/8+ε/82O(εn)O(1/ε)εn2εn7/8

Chodzi o to, że istnieje jakiś blok zmiennej, taki że optymalne przypisanie (ograniczone do tego bloku) już spełnia ułamek maksymalnej liczby spełnionych klauzul. Dostaniesz te dodatkowe klauzule dokładnie poprawne, a otrzymasz 7 / 8 z pozostałą frakcją optimum przy użyciu Karloff i Zwick.ε7/8

Interesujące jest pytanie, czy można uzyskać czas dla tego samego rodzaju przybliżenia. Istnieje „liniowa hipoteza PCP”, że 3SAT można zredukować w czasie wielomianowym do MAX3SAT, na przykład:2O(ε2n)

  • jeśli instancja 3SAT jest zadowalająca, to instancja MAX3SAT jest całkowicie zadowalająca,
  • 7/8+ε
  • poly(1/ε)

2O(εcm)7/8+εcε2εnεm

Ryan Williams
źródło
7/8
18

Aby nieco powtórzyć to, co napisał Ryan Williams w swoim ostatnim akapicie:

T(n)=2n1o(1)(7/8+1/(loglogn).000001)T(n)2o(n)7/8

Ryan O'Donnell
źródło