Planaritätsbedingungen für planares 1-in-3-SAT

14

Planar 3SAT ist NP-vollständig. Eine planare 3SAT-Instanz ist eine 3SAT-Instanz, für die das unter Verwendung der folgenden Regeln erstellte Diagramm planar ist:

  1. fügen Sie einen Eckpunkt für jeden und ¯ x ixichxich¯
  2. füge einen Vertex für jede Klausel Cj
  3. Addiere eine Kante für jedes (xich,xich¯) Paar
  4. Addiere eine Kante von Vertex (oder ¯ x ixichxich¯ ) zu jedem Scheitelpunkt hinzu, der eine Klausel darstellt, die ihn enthält
  5. füge Kanten zwischen zwei aufeinander folgenden Variablen (x1,x2),(x2,x3),...,(xn,x1)

Insbesondere bildet Regel 5 ein "Rückgrat", das die Klauseln in zwei unterschiedliche Regionen aufteilt.

Planar 1-in-3 SAT ist ebenfalls NP-vollständig.

Sind die Planaritätsbedingungen für planares 1-in-3-SAT jedoch wie in Planar 3SAT definiert? Können wir insbesondere davon ausgehen, dass es ein Backbone gibt, das die Variablen verknüpft ? (xich,xich+1)
Vor
quelle
1
Nur für den Fall, dass jemand nach dem Papier suchen würde, bei dem er die Härte von Planar 1-in-3SAT (weniger starke Version) aufweist. Hier ist ein Link: dl.acm.org/citation.cfm?doid=1137856.1137859 Aus ihrem Beweis kann man ersehen, dass die "Backbone" -Anforderung leicht erfüllt wird.
sud03r

Antworten:

8

Ja, du kannst. Man kann sogar beweisen, dass etwas Stärkeres wahr ist. Das als Positive Planar 1-in-3-SAT bekannte Problem ist NP-vollständig, wie von Mulzer und Rote gezeigt .

In dieser Version von 1-in-3-SAT benötigen Sie für jede Eingabeformel das

  • Sie haben drei Variablen pro Klausel, von denen keine negiert wird
  • Das Diagramm der Formel ist eben, auch wenn Sie das "Backbone" zwischen den variablen Scheitelpunkten hinzufügen

Die Reduktion ist von Planar 3-SAT .

A.Schulz
quelle