Odnaleźć

9

Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.Lϵ2φ(12+ϵ)φ

Muszę udowodnić, że istnieje st is twardy dla każdego .ϵLϵNPϵ<ϵ

Wiemy, że może być przybliżony do presetów klauzul z redukcji . Jak mam to rozwiązać?Max2Sat5556Max3Sat

Joni
źródło

Odpowiedzi:

8

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ąα zadowalające i przypadki, które są (22/21)α zadowalające dla niektórych α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¬a). Liczby stają się teraz1/2+p(α1/2) i 1/2+p((22/21)α1/2). Ten ostatni numer można podać tak blisko1/2 jak chcemy.

Yuval Filmus
źródło
Czy twoja metoda działa, gdy ε jest dowolną (ale wystarczająco małą) liczbą rzeczywistą? Nie mogę wymyślić, jak wybrać odpowiednią liczbę klauzul do użycia dla dopełnienia, chyba że założę coś o ε. (Zauważ, że ε nie jest częścią danych wejściowych, a zatem dobrze jest brać pod uwagę liczbę rzeczywistą ε.)
Tsuyoshi Ito,
To jest różnica między nimi 1/2+p(α1/2) i 1/2+p((22/21)α1/2)może być przydatne. Zarozumiałyα jest racjonalny, weź trochę racjonalny pi powinieneś sobie poradzić.
Yuval Filmus
Aha, jakoś pomyślałem, że ta metoda nie zadziałała, kiedy wypróbowałem ją najpierw, ale teraz widzę, jak to działa. Dzięki!
Tsuyoshi Ito,
5

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.

Tsuyoshi Ito
źródło