Komplexität des Problems (SAT zu 3-SAT)?

7

Es ist bekannt, dass jede CNF-Formel in Polynomzeit unter Verwendung neuer Variablen in eine 3-CNF-Formel umgewandelt werden kann ( siehe hier ). Wenn die Verwendung neuer Variablen nicht zulässig ist, ist dies nicht immer möglich (nehmen Sie zum Beispiel die Einzelklauselformel: ).(x1∨x2∨x3∨x4)

Definieren wir das Problem (SAT bis 3-SAT): Gegeben ist , eine CNF-Formel. Ist es möglich, in einen äquivalenten 3-CNF umzuwandeln, der auf denselben Variablen wie ? - wobei "äquivalent" mit demselben Modellsatz bedeutet.F.F.F.

Was ist die Komplexität dieses Problems?

Bearbeiten : Es wurde in der Theorie gezeigt, dass das Problem Co-NP schwer ist.

complexity-theory satisfiability decision-problem complexity-classes Xavier Labouze
quelle
5
Es ist nicht immer möglich, sich zu transformieren F., eine allgemeine CNF-Formel definiert auf n Variablen in eine 3-CNF-Formel definiert n Variablen als F..
Xavier Labouze
4
Wählen Sie einfach eine einzelne Klauselformel F.=x1∨x2∨x3∨x4
Vor dem
Es ist nach dem Lösen des Sat möglich. Dann können Sie jedes k-sat konstruieren, ohne neue Variablen hinzuzufügen. Die Komplexität dieses Problems ist also die Komplexität der Lösung von sat.
Ilya Gazman
@ Babibu - Kannst du das näher erläutern? (Ich habe gerade die Frage bearbeitet, um sie mit der Antwort auf cstheory zu verknüpfen, die zeigt, dass das Problem co-np schwer ist und um genau zu sagen, dass "äquivalent" mit demselben Satz von Modellen bedeutet).
Xavier Labouze
Was meinst du mit Transformation ? Ich denke, es gibt eine PSPACE-Obergrenze, wenn das Problem darin besteht, die Existenz einer 3CNF-Formel zu überprüfen, die (mit demselben Modellsatz) einer bestimmten Formel in CNF entspricht
Pablo Munoz

Antworten:

3

Dies wurde auf der CS Theory StackExchange-Website beantwortet: https://cstheory.stackexchange.com/a/19833/5038

(Ich poste hier eine Antwort, damit diese Frage nicht als Frage ohne Antwort behandelt wird und vom Community-Benutzer regelmäßig auf die Startseite zurückgedreht wird. Normalerweise werden Fragen ohne positive oder akzeptierte Antwort erneut beantwortet - wird von Zeit zu Zeit auf der Titelseite angezeigt. Da diese Frage jetzt an anderer Stelle beantwortet wurde, scheint dies nicht erforderlich zu sein. Solange jemand diese Antwort positiv bewertet oder akzeptiert, sollte dies verhindern, dass diese Frage erneut bearbeitet wird Ich kreuze das Community-Wiki-Kästchen an, damit ich von dieser Antwort keine Wiederholung bekomme.)

D.W.
quelle
Tks für Ihr Anliegen: +1
Xavier Labouze