Definicja Planar 3-SAT

Co było mylące w wynikach?

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ą?

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 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?

$x_i$$+x_i$$-x_i$