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

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żdego$x_i$ i $\bar{x_i}$
2. dodać wierzchołek dla każdej klauzuli $C_j$
3. dodaj krawędź dla każdej pary $(x_i,\bar{x_i})$
4. dodaj krawędź z wierzchołka (lub ¯ x i ) do każdego wierzchołka reprezentującego klauzulę, która go zawiera$x_i$$\bar{x_i}$
5. dodać krawędzi między dwoma następującymi po sobie zmienne $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

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.

$(x_i,x_{i+1})$

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 .