Ich versuche, eine Aufgabe zu erarbeiten (entnommen aus dem Buch Algorithmen - von S. Dasgupta, CH Papadimitriou und UV Vazirani , Kapitel 8, Problem 8.6a), und paraphrasiere, was darin steht:
Angesichts der Tatsache, dass 3SAT auch dann NP-vollständig bleibt, wenn es auf Formeln beschränkt ist, in denen jedes Literal höchstens zweimal vorkommt, zeigen Sie, dass das Problem in Polynomzeit lösbar ist, wenn jedes Literal höchstens einmal vorkommt.
Ich habe versucht, dies zu lösen, indem ich die Klauseln in mehrere Gruppen unterteilt habe:
- Klauseln, die keine Variable mit den übrigen Klauseln gemeinsam hatten
- Klauseln, die nur 1 Variable gemeinsam hatten
- Klauseln, die 2 Variablen gemeinsam hatten
- Klauseln, die alle 3 Variablen gemeinsam hatten
Meine Argumentation wurde in der Richtung versucht, dass die Anzahl solcher Gruppen endlich ist (aufgrund der auferlegten Einschränkung, dass kein Literal mehr als einmal vorhanden ist), und wir könnten versuchen, zuerst die am stärksten eingeschränkte Gruppe zu befriedigen (Gruppe 4) und dann die zu ersetzen führen zu den weniger eingeschränkten Gruppen (3, 2 und dann 1), aber ich erkannte, dass dies mich nicht ganz weiter brachte, da dies nicht viel von dem Fall für die eingeschränkte Version von 3SAT abweicht, in der jedes Literal erscheinen kann höchstens zweimal, was sich als NP-vollständig 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 keinen ausreichenden Sinn ergab, den ich hier wörtlich wiedergebe:
Hinweis: Da jedes Literal höchstens einmal vorkommt, konvertieren Sie dieses Problem in ein 2SAT-Problem - daher Polynomzeit, wenn ein Literal in Klausel und ein Komplement von (dh ) in Klausel , konstruieren Sie eine neue Klausel Klausel . CkCj∨ ¯ C k
Sowohl als auch haben jeweils drei Literale - ich habe nicht verstanden, wie ich es in 2SAT konvertieren soll, indem ich (oder wenn ich es falsch gelesen habe) .C k C j ∨ ¯ C k ¯ C j ∨ C k
Jede Hilfe beim Entschlüsseln des Hinweises oder beim Bereitstellen eines Pfades, den ich erkunden kann, wäre sehr dankbar.
quelle