Ist eine "lokale" Version von 3-SAT NP-hard?

7

Nachfolgend meine Vereinfachung eines Teils eines größeren Forschungsprojekts zu räumlichen Bayes'schen Netzwerken:

Angenommen, eine Variable ist " -local" in einer Zeichenfolge wenn zwischen dem ersten und dem letzten Satz, in dem sie vorkommt, weniger als Klauseln stehen (wobei eine natürliche Zahl ist).kC3-CNFkk

Betrachten Sie nun die Teilmenge die durch das Kriterium definiert ist, dass für jedes jede Variable in ist lokal. Für welches (falls vorhanden) ist NP-hart?(3,k)-LSAT3-SATC(3,k)-LSATCkk(3,k)-LSAT


Folgendes habe ich bisher in Betracht gezogen:

(1) Variationen der Methode zum Zeigen, dass in P ist, indem jede Disjunktion als Implikation und gerichtete Pfade auf dem gerichteten Graphen dieser Implikationen untersucht werden ( hier angegeben und ausführlich auf S. 184 dargestellt) 185 von Papadimitrious Computerkomplexität ). Anders als in gibt es eine Verzweigung der gerichteten Pfade in , aber möglicherweise ist die Anzahl der gerichteten Pfade durch die räumlichen Einschränkungen der Variablen begrenzt. Bisher kein Erfolg damit.2-SAT2-SAT(3,k)-LSAT

(2) Eine Polynomzeitreduktion von (oder einem anderen bekannten NP-vollständigen Problem) auf . Zum Beispiel habe ich verschiedene Schemata zur Einführung neuer Variablen ausprobiert. Um die Klauseln zusammenzuführen, die die ursprüngliche Variable enthalten , muss ich jedoch im Allgemeinen "Ketten" zusätzlicher Klauseln ziehen, die die neuen Variablen enthalten, und diese beeinträchtigen die räumlichen Einschränkungen für die anderen Variablen.3-SAT(3,k)-LSATxk

Sicher bin ich hier nicht auf Neuland. Gibt es ein bekanntes NP-hartes Problem, das auf reduziert werden kann, oder verhindern die räumlichen Einschränkungen, dass das Problem so schwierig ist?(3,k)-LSAT

SapereAude
quelle

Antworten:

13

(3,k)-LSAT ist in P für alle . Wie Sie angegeben haben, ist die Lokalität ein großes Hindernis für die Vollständigkeit der NP.k


Hier ist ein Polynomalgorithmus.

Eingabe: , , wobei die Klausel ist. Ausgabe: true, wenn unter einer Zuweisung aller Variablen zu 1 wird. Verfahren:ϕ(3,k)-LSATϕ=c1c2cmcii
ϕ

  1. Konstruieren Sie die Menge , die Variablen, die in mindestens einer von , .Bici,ci+1,,ci+k1imk
  2. Konstruiere die Menge .Ai={f:Bi{0,1}ci,ci+1,,ci+k become 1 underf}
  3. Konstruiere die MengeE=i{(f,g)fAi,gAi+1,f(x)=g(x) for all xBiBi+1}
  4. Sei . Betrachten Sie den gerichteten Graphen . Starten Sie für jeden Scheitelpunkt in eine Tiefensuche auf um festzustellen, ob wir einen Scheitelpunkt in . Wenn gefunden, geben Sie true zurück.V=A1A2AmkG(V,E)A1GAmk
  5. Wenn wir hier angekommen sind, geben Sie false zurück.

Die Richtigkeit des obigen Algorithmus ergibt sich aus der folgenden Behauptung.

Anspruch. ist erfüllbar gibt es in einen Pfad von einem Scheitelpunkt in zu einem Scheitelpunkt in . Beweis. " ": Angenommen, wird unter Zuweisung zu 1 . Sei die Beschränkung von auf . Dann haben wir einen Pfad . " ": Angenommen, es gibt einen Pfad , wobei und . Zuordnung definierenϕGA1Amk

ϕffifBif1,,fmk
f1,,fmkf1A1fmkAmkf so, dass mit allen übereinstimmt , dh wenn . Wir können überprüfen, ob gut definiert ist. Da für einige für alle 1 wird , wird unter 1 .ffif(x)=fi(x)xBifcfjϕf


Die Anzahl der Eckpunkte . Daher läuft der Algorithmus in Polynomzeit in Form von , der Anzahl der Klauseln und , der Anzahl der Gesamtvariablen.|V|23(k+1)(mk)mn

John L.
quelle
In Schritt 4 sollte "für jeden Scheitelpunkt in " besser "von jedem Scheitelpunkt in " sein. A1A1
John L.
Diese Methode ist sehr hilfreich. Es ist mir peinlich, dass ich es vor Ihrem Beitrag nicht gesehen habe. Kennen Sie zufällig eine Referenz (Lehrbuch, Artikel usw.), in der sie erscheint?
SapereAude
1
Ich befürchte, dass ich mich an keinen direkten Hinweis erinnern kann. Es ist jedoch ein Hauptthema in der Mathematik, dass eine globale Lösung manchmal aus lokalen Lösungen zusammengesetzt werden kann.
John L.