Maks/min Twierdzenia klasyfikacyjne CSP/Jedynki
W teorii złożoności obliczeniowej , gałęzi informatyki , twierdzenia klasyfikacyjne Max/min CSP/One określają warunki konieczne i wystarczające, które określają klasy złożoności problemów o spełnieniu podzbioru S relacji boolowskich. Są podobne do twierdzenia o dychotomii Schaefera , które klasyfikuje złożoność spełniania skończonych zbiorów relacji; jednak twierdzenia klasyfikacyjne Max/min CSP/Jedynki dostarczają informacji o złożoności aproksymacji optymalnego rozwiązania problemu zdefiniowanego przez S. _
Mając zbiór S klauzul, problem spełnienia ograniczeń Max (CSP) polega na znalezieniu maksymalnej liczby (w przypadku ważonym: maksymalnej sumy wag) spełnialnych klauzul w S . Podobnie problemem Min CSP jest zminimalizowanie liczby klauzul niespełnionych. Problem Max Ones polega na zmaksymalizowaniu liczby zmiennych boolowskich w S , które są ustawione na 1 przy zastrzeżeniu, że wszystkie klauzule są spełnione, a problem Min Ones polega na zminimalizowaniu tej liczby.
W przypadku korzystania z poniższych klasyfikacji klasa złożoności problemu jest określana na podstawie najwyższej klasyfikacji, którą spełnia .
Definicje
Dla zwięzłości definiujemy tutaj niektóre terminy, które są używane w poniższych klasyfikacjach.
- PO oznacza optymalizację czasu wielomianu ; problemy, dla których znalezienie optimum można przeprowadzić w czasie wielomianowym, tak że przybliżenie do dowolnej precyzji można również wyraźnie przeprowadzić w czasie wielomianowym.
- Koniunkcyjna postać normalna jest poniżej skrótem CNF .
- X(N)OR-SAT oznacza problem spełnialności, który jest AND kilku boolowskich równań liniowych, które można zapisać jako klauzule XOR. Dokładnie jeden literał w każdej klauzuli XOR musi zostać zanegowany (np. . Zobacz XOR-SAT .
- Min UnCut-complete odnosi się do klasy złożoności historycznie zdefiniowanej w kategoriach problemu o nazwie Min UnCut. problemy są - trudne z
- Min 2CNF-Deletion-complete to kolejna klasa złożoności historycznie zdefiniowana przez problem. ale mają przybliżenie
- Nearest Codeword-complete to kolejna taka klasa złożoności. Takich problemów nie można przybliżyć do współczynnika dla .
- Min Horn-Deletion-complete to kolejna taka klasa złożoności. Takich problemów nie da się przybliżyć do współczynnika dla pewnego , więc mają pewne przybliżenie współczynnika wielomianu.
Twierdzenia klasyfikacyjne
Maks. CSP
Następujące warunki składają się na twierdzenie klasyfikacyjne dla problemów Max CSP.
- Jeśli ustawienie wszystkich zmiennych na wartość true lub wszystkich zmiennych na wartość false spełnia wszystkie klauzule, jest to w PO.
- Jeśli wszystkie klauzule po konwersji do postaci normalnej dysjunkcyjnej mają dwa terminy, jeden składający się ze wszystkich zmiennych dodatnich (niezanegowanych), a drugi ze wszystkich zmiennych zanegowanych, to jest w PO.
- W przeciwnym razie problem jest APX-complete .
Max Ones
Następujące warunki składają się na twierdzenie klasyfikacyjne dla problemów Max Ones.
- Jeśli ustawienie wszystkich zmiennych na true spełnia wszystkie klauzule, to jest w PO.
- Jeśli każdą klauzulę można zapisać jako CNF podrozdziałów Dual-Horn , to jest ona w PO.
- Jeśli jest to instancja 2-X(N)OR-SAT, czyli X(N)OR-SAT z dwiema zmiennymi na równanie liniowe, to jest w PO.
- Jeśli jest to instancja X(N)OR-SAT, ale nie 2-X(N)OR-SAT, jest to APX-complete.
- Jeśli każdą klauzulę można zapisać jako CNF podrozdziałów Horna , to jest to Poly-APX-complete .
- Jeśli jest to instancja 2-CNF-SAT , to jest to Poly-APX-complete.
- Jeśli ustawienie wszystkich lub wszystkich oprócz jednej zmiennej false spełnia każdą klauzulę, jest to Poly-APX-complete.
- Odróżnienie odpowiedzi 0 od odpowiedzi niezerowej jest NP-trudne, jeśli ustawienie wszystkich zmiennych na fałsz spełnia wszystkie klauzule.
- W przeciwnym razie znalezienie nawet wykonalnego rozwiązania jest NP-trudne.
Min CSP
Następujące warunki składają się na twierdzenie klasyfikacyjne dla problemów Min CSP.
- Jeśli ustawienie wszystkich zmiennych na fałsz lub wszystkich zmiennych na prawdę spełnia wszystkie klauzule, to jest w PO.
- Jeśli wszystkie klauzule po konwersji do postaci normalnej dysjunkcyjnej mają dwa terminy, jeden składający się ze wszystkich zmiennych dodatnich (niezanegowanych), a drugi ze wszystkich zmiennych zanegowanych, to jest w PO.
- Jeśli wszystkie klauzule są LUB zmiennych O(1), jest to APX-zupełne.
- Jeśli jest to instancja 2-X(N)OR-SAT, jest to Min UnCut-complete.
- Jeśli jest to instancja X(N)OR-SAT, ale nie 2-X(N)OR-SAT, jest to najbliższe słowo kodowe-kompletne.
- Jeśli jest to instancja 2-CNF-SAT , to Min 2CNF-Deletion-complete.
- Jeśli wszystkie klauzule to Horn lub Dual-Horn , to Min Horn Deletion-complete.
- W przeciwnym razie rozróżnienie między odpowiedzią 0 a odpowiedzią niezerową jest NP-zupełne.
Min. jedynki
Następujące warunki składają się na twierdzenie klasyfikacyjne dla problemów Min Ones.
- Jeśli ustawienie wszystkich zmiennych na false spełnia wszystkie klauzule, to jest w PO.
- Jeśli każdą klauzulę można zapisać jako CNF podklauzul Horna , to jest ona w PO.
- Jeśli jest to instancja 2-X(N)OR-SAT, to jest w PO.
- Jeśli jest to instancja 2-CNF-SAT , jest kompletna APX.
- Jeśli wszystkie klauzule są LUB zmiennych O(1), jest to APX-zupełne.
- Jeśli jest to instancja X(N)OR-SAT, ale nie 2-X(N)OR-SAT, jest to najbliższe słowo kodowe-kompletne.
- Jeśli każda klauzula może być zapisana jako CNF podklauzul Dual-Horn , to jest to Min Horn Deletion-complete.
- Jeśli ustawienie wszystkich zmiennych na wartość true spełnia wszystkie klauzule, jest to Poly-APX-complete.
- W przeciwnym razie znalezienie wykonalnego rozwiązania jest NP-trudne.