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.

  1. Jeśli ustawienie wszystkich zmiennych na wartość true lub wszystkich zmiennych na wartość false spełnia wszystkie klauzule, jest to w PO.
  2. 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.
  3. W przeciwnym razie problem jest APX-complete .

Max Ones

Następujące warunki składają się na twierdzenie klasyfikacyjne dla problemów Max Ones.

  1. Jeśli ustawienie wszystkich zmiennych na true spełnia wszystkie klauzule, to jest w PO.
  2. Jeśli każdą klauzulę można zapisać jako CNF podrozdziałów Dual-Horn , to jest ona w PO.
  3. 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.
  4. Jeśli jest to instancja X(N)OR-SAT, ale nie 2-X(N)OR-SAT, jest to APX-complete.
  5. Jeśli każdą klauzulę można zapisać jako CNF podrozdziałów Horna , to jest to Poly-APX-complete .
  6. Jeśli jest to instancja 2-CNF-SAT , to jest to Poly-APX-complete.
  7. Jeśli ustawienie wszystkich lub wszystkich oprócz jednej zmiennej false spełnia każdą klauzulę, jest to Poly-APX-complete.
  8. Odróżnienie odpowiedzi 0 od odpowiedzi niezerowej jest NP-trudne, jeśli ustawienie wszystkich zmiennych na fałsz spełnia wszystkie klauzule.
  9. 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.

  1. Jeśli ustawienie wszystkich zmiennych na fałsz lub wszystkich zmiennych na prawdę spełnia wszystkie klauzule, to jest w PO.
  2. 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.
  3. Jeśli wszystkie klauzule są LUB zmiennych O(1), jest to APX-zupełne.
  4. Jeśli jest to instancja 2-X(N)OR-SAT, jest to Min UnCut-complete.
  5. Jeśli jest to instancja X(N)OR-SAT, ale nie 2-X(N)OR-SAT, jest to najbliższe słowo kodowe-kompletne.
  6. Jeśli jest to instancja 2-CNF-SAT , to Min 2CNF-Deletion-complete.
  7. Jeśli wszystkie klauzule to Horn lub Dual-Horn , to Min Horn Deletion-complete.
  8. 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.

  1. Jeśli ustawienie wszystkich zmiennych na false spełnia wszystkie klauzule, to jest w PO.
  2. Jeśli każdą klauzulę można zapisać jako CNF podklauzul Horna , to jest ona w PO.
  3. Jeśli jest to instancja 2-X(N)OR-SAT, to jest w PO.
  4. Jeśli jest to instancja 2-CNF-SAT , jest kompletna APX.
  5. Jeśli wszystkie klauzule są LUB zmiennych O(1), jest to APX-zupełne.
  6. Jeśli jest to instancja X(N)OR-SAT, ale nie 2-X(N)OR-SAT, jest to najbliższe słowo kodowe-kompletne.
  7. Jeśli każda klauzula może być zapisana jako CNF podklauzul Dual-Horn , to jest to Min Horn Deletion-complete.
  8. Jeśli ustawienie wszystkich zmiennych na wartość true spełnia wszystkie klauzule, jest to Poly-APX-complete.
  9. W przeciwnym razie znalezienie wykonalnego rozwiązania jest NP-trudne.

Zobacz też