Definicja Planar 3-SAT

Jaka jest standardowa definicja Planar 3-SAT? Widziałem wiele różnych definicji. Jaki był oryginalny dokument, który go zdefiniował i udowodnił, że jest NP-kompletny?

— użytkownik24175
źródło

Co było mylące w wynikach?

— Niel de Beaudrap,

Widzę różne definicje, jak niektórzy mówią: Dwustronny wykres między klauzulami i literałami musi być płaski (nie wiem przez literały, czy oznaczają one tylko x_i lub oba x_i i jego negację, to znaczy nie wiem, co jest ich wykres gadżetu dokładnie tutaj?). Niektóre inne definiują dla niego dwa typy: tylko dwustronne krawędzie między klauzulami i literałami lub te plus (x_i, ~ x_i). Lub jakaś inna mówi, powyższy wykres plus (x_i, x_ {i + 1})? Nie mogę nawet znaleźć oryginalnego artykułu na nim opublikowanego? Zasadniczo nie mogę znaleźć dobrego odniesienia z idealną definicją?

— user24175,

Pierwotne odniesienie to: D. Lichtenstein, „Formuły planarne i ich zastosowania” (1982) ; ale istnieje wiele małych odmian, które wciąż są kompletne z NP (dowód większości z nich jest łatwy).

— Marzio De Biasi

@Marzio De Biasi Dziękuję bardzo! Ale w oparciu o ten układ planarny 3-SAT jest przypadkiem, gdy dwustronny wykres między klauzulami, że literały (tylko x_i nie są ich negacjami) jest płaski. Dobrze? Możemy łatwo dojść do wniosku, że uwzględniamy również negację x_i, po prostu dodając między nimi przewagę, nie zakłócając płaskości, prawda?

— user24175,

x_{i}

$x_i$

+ x_{i}

$+x_i$

- x_{i}

$-x_i$

Na stronie http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf znajduje się niezła kompilacja definicji pokrewnych NP-kompletnych problemów z planarnością

Jeden z nich, płaski monotoniczny 3-sat, pozwala podzielić każdy terminal na dodatni i ujemny, z terminalami umieszczonymi wzdłuż linii z częścią dodatnią po jednej stronie linii i częścią ujemną po drugiej stronie linii. Klauzule mają tylko dodatnie lub tylko ujemne końcówki i są umieszczone odpowiednio po dodatniej lub ujemnej stronie linii.

— David Eppstein
źródło