Warunki płaskości dla Planar 1-in-3 SAT

14

Planar 3SAT jest kompletny z NP. Płaska instancja 3SAT jest instancją 3SAT, dla której wykres zbudowany przy użyciu następujących reguł jest płaski:

  1. dodaj wierzchołek dla każdegoxi i xi¯
  2. dodać wierzchołek dla każdej klauzuli Cj
  3. dodaj krawędź dla każdej pary (xi,xi¯)
  4. dodaj krawędź z wierzchołka (lub ¯ x i ) do każdego wierzchołka reprezentującego klauzulę, która go zawieraxixi¯
  5. dodać krawędzi między dwoma następującymi po sobie zmienne (x1,x2)),(x2),x3)),...,(xn,x1)

W szczególności reguła 5 tworzy „kręgosłup”, który dzieli klauzule na dwa odrębne regiony.

Planar 1-w-3 SAT jest również NP-kompletny.

(xja,xja+1)
Vor
źródło
1
Na wszelki wypadek, gdyby ktoś szukał papieru, w którym wykazuje twardość Planar 1-w-3SAT (wersja mniej mocna ). Oto link: dl.acm.org/citation.cfm?doid=1137856.1137859 Z ich dowodu widać, że wymóg „kręgosłupa” jest łatwo spełniony.
sud03r

Odpowiedzi:

8

Tak, możesz. W rzeczywistości możesz nawet pokazać, że coś silniejszego jest prawdą. Problem znany jako Positive Planar 1-in-3-SAT jest NP-zupełny, jak pokazują Mulzer i Rote .

W tej wersji 1-w-3-SAT potrzebujesz każdej formuły wejściowej, która

  • masz trzy zmienne na klauzulę, żadna z nich nie jest zanegowana
  • wykres formuły jest płaski, nawet jeśli dodasz „kręgosłup” między zmiennymi wierzchołkami

Redukcja pochodzi z Planar 3-SAT .

A.Schulz
źródło