Odnaleźć

Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.$L_\epsilon$$2$$\varphi$$(\frac{1}{2}+\epsilon)$$\varphi$

Muszę udowodnić, że istnieje st is twardy dla każdego .$\epsilon'$$L_\epsilon$$\mathsf{NP}$$\epsilon<\epsilon'$

Wiemy, że może być przybliżony do presetów klauzul z redukcji . Jak mam to rozwiązać?$\text{Max}2\text{Sat}$$\frac{55}{56}$$\text{Max}3\text{Sat}$

W swoim słynnym artykule Håstad pokazuje, że NP-trudne jest przybliżenie MAX2SAT lepiej niż$21/22$ . To prawdopodobnie oznacza, że ​​trudno jest odróżnić instancje, które są$\leq \alpha$ zadowalające i przypadki, które są $\geq (22/21) \alpha$ zadowalające dla niektórych $\alpha \geq 1/2$. Teraz wyobraź sobie, że wstawiasz instancję, aby stała się$p$-frakcja nowej instancji, której reszta jest dokładnie $1/2$-satisfiable (powiedzmy, że składa się z grup klauzul formularza) $a \land \lnot a$). Liczby stają się teraz$1/2 + p (\alpha - 1/2)$ i $1/2 + p((22/21)\alpha - 1/2)$. Ten ostatni numer można podać tak blisko$1/2$ jak chcemy.

Jeśli wiesz, że ε jest liczbą wymierną, nie potrzebujesz niedokładności, aby Max-2-SAT mógł udowodnić swoje twierdzenie. Typowy dowód twardości NP dla Max-2-SAT (np. Ten w podręczniku Compadational Complexity by Papadimitriou) faktycznie dowodzi kompletności NP dla L _1/5 . Aby udowodnić twardość NP L _ε dla dodatnich liczb wymiernych ε <1/5, możemy zmniejszyć L _1/5 do L _ε w następujący sposób: biorąc pod uwagę wzór 2CNF φ (przykład dla L _1/5 ), niech m będzie liczba zawartych w nim klauzul. Niech r is są dodatnimi liczbami całkowitymi takimi, że (1 / 5− ε ) mr = 2 ε s utrzymuje. Następnie skonstruuj wzór 2CNF (instancja dla L _ε ), powtarzając φ dla r razy i dodając s pary sprzecznych zdań. Proste obliczenie pokazuje, że rzeczywiście jest to redukcja z L _1/5 do L _ε .

Redukcja ta wyraźnie działa tylko wtedy, gdy ε jest racjonalne, ponieważ w przeciwnym razie r i s nie może być traktowane jako liczby całkowite. Ogólny przypadek, w którym ε niekoniecznie jest racjonalny, wydaje się wymagać niedoceniania, jak napisał Yuval Filmus w swojej odpowiedzi.