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:
- dodaj wierzchołek dla każdego i
- dodać wierzchołek dla każdej klauzuli
- dodaj krawędź dla każdej pary
- dodaj krawędź z wierzchołka (lub ¯ x i ) do każdego wierzchołka reprezentującego klauzulę, która go zawiera
- dodać krawędzi między dwoma następującymi po sobie zmienne
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.
Odpowiedzi:
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
Redukcja pochodzi z Planar 3-SAT .
źródło