Definition von Planar 3-SAT

Was hat Sie an den Ergebnissen verwirrt?

Ich sehe verschiedene Definitionen, wie manche sagen: Der zweigliedrige Graph zwischen Klauseln und den Literalen muss planar sein (ich weiß nicht, ob Literale nur x_is oder beide x_i und seine Negation bedeuten, ich meine, ich weiß nicht, was ihre sind Gadget-Grafik genau hier?). Einige andere definieren zwei Typen dafür: nur die zweigliedrigen Kanten zwischen Klauseln und Literalen oder diese Pluszeichen (x_i, ~ x_i). Oder sagt ein anderer, der obige Graph plus die (x_i, x_ {i + 1})? Ich kann nicht einmal das darauf veröffentlichte Originalpapier finden? Grundsätzlich kann ich keine gute Referenz mit einer perfekten Definition dafür finden?

Die ursprüngliche Referenz lautet: D. Lichtenstein, "Planare Formeln und ihre Verwendung" (1982) ; Es gibt jedoch viele kleine Variationen, die noch NP-vollständig sind (der NPC-Beweis für die meisten von ihnen ist einfach).

@ Marzio De Biasi Vielen Dank! Basierend auf diesem Paer ist planares 3-SAT jedoch der Fall, dass der zweigeteilte Graph zwischen den Klauseln, dass Literale (nur x_i sind nicht ihre Negationen) planar sind. Recht? Wir können leicht den Fall schließen, dass wir auch die Negation von x_i einbeziehen, indem wir einfach eine Kante zwischen ihnen hinzufügen, ohne die Planarität zu stören, oder?

$x_i$$+x_i$$-x_i$