Algorytmy aproksymacji super wielomianu dla MAX 3SAT

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+ \epsilon$$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/8$$7/8+ \epsilon$$n^{O(\log n)}$$2^{o(n)}$

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+\varepsilon/8$$2^{O(\varepsilon n)}$$O(1/\varepsilon)$$\varepsilon n$$2^{\varepsilon n}$$7/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.$\varepsilon$$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:$2^{O(\varepsilon^2 n)}$

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

$2^{O(\varepsilon^c m)}$$7/8+\varepsilon$$c$$\varepsilon$$2^{\varepsilon n}$$\varepsilon$$m$

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

$T(n) = 2^{n^{1-o(1)}}$$(7/8 + 1/(\log \log n)^{.000001})$$T(n)$$2^{o(n)}$$7/8$