Wie kann man beweisen, dass eine eingeschränkte Version von 3SAT, in der kein wörtliches Auftritt mehr als einmal auftreten kann, in Polynomzeit lösbar ist?

Question

Ich versuche, einen Auftrag auszuarbeiten (aus dem Buch entnommen Algorithmen - von S. Dasgupta, Ch Papadimitriu und UV Vazirani, Kap. 8, Problem 8.6a), und ich paraphrasiere das, was es heißt:

Angesichts der Tatsache, dass 3SAT NP-Complete bleibt, auch wenn sie auf Formeln beschränkt sind, in denen jedes wörtliche Treffer zweimal erscheint, zeigen Sie, dass das Problem in der Polynomzeit lösbar ist, wenn jedes wörtliche Literal erscheint.

Ich habe versucht, dies zu lösen, indem ich die Klauseln in mehrere Gruppen unterteilte:

1. Klauseln, die mit den Resten der Klauseln keine Variable hatten
2. Klauseln, die nur 1 Variable gemeinsam hatten
3. Klauseln, die 2 Variablen gemeinsam hatten
4. Klauseln, die alle 3 Variablen gemeinsam hatten

Meine Argumentation wurde in der Sicht versucht, dass die Anzahl solcher Gruppen endlich ist (aufgrund der auferlegten Einschränkung, dass kein wörtlicher Grund mehr als einmal vorhanden ist), und wir konnten versuchen, zuerst die am meisten eingeschränkte Gruppe zu befriedigen (Gruppe 4) und dann die ersetzen führen zu den weniger eingeschränkten Gruppen (3, 2 und dann 1), aber ich wurde festgestellt höchstens zweimal, was sich als NP-Vervollständigung erwiesen hat.

Ich habe versucht, online nach Hinweisen/Lösungen zu suchen, aber alles, was ich bekommen konnte, war dieser Link, in dem der angegebene Hinweis für mich nicht ausreichend Sinn machte, was ich hier wörtlich reproduziere:

Hinweis: Da jedes wörtliche Literal höchstens auftritt, konvertieren Sie dieses Problem in das 2SAT -Problem - daher erscheint Polynomzeit, wenn ein wörtlicher $ x_i $ in Abschnitt $ C_J $ und ergänzt von $ x_i $ (dh $ overline {x_i} $) Konstruieren Sie in Klausel $ C_K $ eine neue Klauselklausel $ c_j lor overline {c_k} $.

Sowohl $ c_j $ als auch $ c_k $ haben jeweils drei Literale - ich habe nicht bekommen, wie ich es in 2SAT konvertieren sollte, indem ich $ c_j lor overline {c_k} $ (oder $ overline {c_j lor c_k} mache $ wenn ich es falsch gelesen habe).

Jede Hilfe beim Entschlüsseln des Hinweises oder die Bereitstellung eines Weges, den ich erkunden kann, wäre sehr geschätzt.

Answer 1

Ohne Verlust der Allgemeinheit können wir davon ausgehen, dass jede Variablen genau einmal positiv und genau einmal negativ erscheint (wenn eine Variable erst einmal angezeigt wird, sobald sie ihren Wert festgelegt hat, um die Klausel zu erfüllen und die Klausel zu entfernen). Wir können auch davon ausgehen, dass eine Variable nicht mehr als einmal in einer Klausel erscheint (wenn eine Variable sowohl positiv als auch negativ in einer Klausel erscheint, ist die Klausel erfüllt und kann entfernt werden). Diese werden die Erfüllbarkeit nicht verändern.

Verwenden Sie nun die Auflösungsregel Um die Variablen einzeln zu beseitigen (da jede Variable genau einmal positiv und einmal negativ erscheint, ist dies ein deterministischer Prozess). Wenn wir zu irgendeinem Zeitpunkt die leere Klausel erhalten, ist die Klauseln nicht zufriedenstellbar, andernfalls ist sie zufriedenbar. Das ist weil:

• Die Auflösung ist ein vollständiges aussagekräftiges Beweissystem (dh wenn eine Klausel logisch durch den Satz von Klauseln impliziert wird, ist sie aus dem Satz von Klauseln nur mit der Auflösungsregel abgeleitet).

• Eine Reihe von Klauseln ist unbefriedigbar, wenn es logischerweise die leere Klausel impliziert.

Dieser Algorithmus benötigt die Polynomzeit, da jede Variable genau einmal aufgelöst wird. Insbesondere reduziert jede Anwendung der Auflösung die Gesamtzahl der Klauseln um eins, sodass die Anzahl der Klauseln nicht zunimmt. Zum Beispiel die Anwendung von Auflösung auf $ (x lor b) land ( overline {x} lor c) land dots) $ ergibt $ (b lor c) land dots $, der eine Klausel weniger hat als vor der Lösung. Wenn Sie dies dagegen auf eine 3SAT -Formel ohne Einschränkung der Anzahl der Erscheinungen jedes Literales angewendet haben, kann die Anwendung der Auflösung dazu führen, dass die Anzahl der Klauseln exponentiell erhöht wird.