Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.
Muszę udowodnić, że istnieje st is twardy dla każdego .
Wiemy, że może być przybliżony do presetów klauzul z redukcji . Jak mam to rozwiązać?
Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.
Muszę udowodnić, że istnieje st is twardy dla każdego .
Wiemy, że może być przybliżony do presetów klauzul z redukcji . Jak mam to rozwiązać?
W swoim słynnym artykule Håstad pokazuje, że NP-trudne jest przybliżenie MAX2SAT lepiej niż . To prawdopodobnie oznacza, że trudno jest odróżnić instancje, które są zadowalające i przypadki, które są zadowalające dla niektórych . Teraz wyobraź sobie, że wstawiasz instancję, aby stała się-frakcja nowej instancji, której reszta jest dokładnie -satisfiable (powiedzmy, że składa się z grup klauzul formularza) ). Liczby stają się teraz i . Ten ostatni numer można podać tak blisko 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.
źródło