Für welches k ist PLANAR NAE k-SAT in P?

23

Das Nicht alle Gleich SAT-Problem (NAE SAT) fragt bei einer Menge von Klauseln über eine Menge von booleschen Variablen, so dass jede Klausel höchstens Literale enthält, ob eine Wahrheitszuordnung der Variablen existiert, so dass Jede Klausel enthält mindestens ein wahres und mindestens ein falsches Literal.k C X kkkCXk

Das PLANARE NAE -SAT-Problem ist die Beschränkung von NAE -SAT auf die Fälle, in denen der bipartite Inzidenzgraph von und (dh der Graph der Teile und mit einer Kante zwischen und wenn und nur wenn oder zu ) gehört, ist planar.k C X C X x X c C x x ckkCXCXxXcCxx¯c

Es ist bekannt, dass NAE 3-SAT NP-vollständig ist (Garey und Johnson, Computer und Intraktabilität; Ein Leitfaden zur Theorie der NP-Vollständigkeit), aber PLANARES NAE 3-SAT ist in P (siehe Planares NAE3SAT ist in P, B) Moret, ACM SIGACT News, Band 19, Ausgabe 2, Sommer 1988 - leider habe ich keinen Zugang zu diesem Artikel).

Ist PLANAR NAE -SAT in P für einige ? Gibt es einen Wert von für den gezeigt wurde, dass er NP-vollständig ist?k 4 kkk4k

Florent Foucaud
quelle

Antworten:

23

PLANAR NAE -SAT ist in P für alle Werte von .kkk

Grund ist, dass wir PLANAR NAE -SAT auf PLANAR NAE -SAT reduzieren können. Sei eine Instanz von PLANAR NAE -SAT und nehme an, dass \ phi eine Klausel C mit den Literalen \ ell_1, \ ell_2, \ dots, \ ell_k enthält . Führen Sie eine neue Variable v_C ein und ersetzen Sie C durch zwei NAE-Klauseln C_1 und C_2 . C_1 enthält 3 Literale \ ell_1 , \ ell_2 und V_c , während C_2 enthält k-1 Literalek3ϕkϕC1,2,,kvCCC1C2C1312vCC2k1v¯C,3,4,,k . Es ist leicht zu erkennen, dass erfüllt werden kann, wenn ist, und dass die Transformation die Planarität beibehält. Jetzt können wir diese Prozedur wiederholt auf die Klauseln anwenden, um gegebenenfalls eine Instanz von NAE -SAT zu erhalten.CC1C2ϕ3

Arnab
quelle
1
Gute Antwort. War das schon bekannt?
Serge Gaspers
1
Es hört sich so an, als würde diese Reduzierung auch ohne die planare Maßgabe "funktionieren", also ist es wahrscheinlich "bekannt"
Suresh Venkat
@Serge Ich bin mir sicher, dass es das war, aber ich kenne keine Referenz.
Arnab
6
Dies ist eine Standardreduzierung, die auch für "normales" SAT funktioniert. Sie finden es zB in Sipsers Buch "Introduction to the Theory of Computation" und in vielen weiteren.
5501