Zeitkomplexität von hochmodernen Sat-Löser in Bezug auf die Länge der Formel

Question

Ich lerne über DPLL und CDCl SAT-Löser, und ich weiß, dass sie Zeitkomplexität exponentiell zur Anzahl der Variablen haben.

Wenn ich nicht irre, einer der Gründe, warum die meisten glauben, dass P nicht gleich NP entspricht, ist, dass es trotz enormer Anstrengung von Mathematikern und Computerwissenschaftlern kein Polynom-Zeitalgorithmus für SAT gibt. Das P-vs-NP-Problem kümmert sich jedoch nur um die Zeitkomplexität in Bezug auf die Länge der Formel, nicht die Anzahl der Variablen.

Wenn diese stationären Sat-Löser auf 3CNF-Formeln ausgeführt wurden, impliziert eine Zeitkomplexität, die für die Anzahl der Variablen, eine Zeitkomplexität, die an der Anzahl der Variablen eine Zeitkomplexität in der Länge der 3CNF ist.

Wenn sie jedoch auf willkürlichen CNFs ausgeführt wurden, deren Länge exponentiell auf die Anzahl der Variablen sein kann, würde eine zeitliche Komplexität exponentiell auf die Anzahl der Variablen nicht notwendigerweise eine zeitliche Komplexität, die exponentiell auf die Länge des CNF ist.

Somit ist eine verwandte Frage, sind diese Sat-Löser auf 3CNF oder CNF während der Messzeitkomplexität?

Answer 1

Für 3sat ist die Anzahl der Variablen polynomisch mit der Anzahl der Klauseln verbunden. (Siehe das Ende für die Rechtfertigung.)

Folglich wäre jeder Algorithmus für 3sat, dessen Laufzeit in der Anzahl der Klauseln Polynom ist, auch in der Anzahl der Variablen Polynome; und jeder Algorithmus für 3sat, dessen Laufzeit Polynom in der Anzahl der Variablen ist, wäre in der Anzahl der Klauseln auch ein Polynom.

Es ist bekannt, dass es einen Polynom-Zeitalgorithmus für 3sat gibt, wenn und nur, wenn und nur ein Polynom-Zeit-Algorithmus für SAT, wenn und nur, wenn und nur, wenn ein Polynom-Zeit-Algorithmus für Circuitsat (z. B. für Formeln) gibt. . Trotz jahrzehntelanger Arbeit an Sat-Löser kennt niemand einen Algorithmus für 3sat, der in der Polynomzeit (oder in der Tat in weniger als exponentiellen Zeit im schlimmsten Fall) läuft. Sie könnten dies als Beweise annehmen, dass es keinen Polynom-Zeitalgorithmus für 3sat gibt; Was bedeutet, dass es keinen Polynom-Zeitalgorithmus für Sat oder Circuitsat gibt, und impliziert auch, dass P!= NP.

---

Begründung: Lassen Sie $ N $ die Anzahl der Variablen und den $ M $ die Anzahl der Klauseln bezeichnen . Wir haben $ n \ le 3m $ (eine Variable, die in keiner Klausel auftritt, kann ignoriert werden) und $ m \ le 8n ^ 3 $ (Jede Klausel hat drei Literale, und Sie können wiederholte Klauseln ignorieren). Daraus folgt, dass $ n / 3 \ le m \ le 8n ^ 3 $ und $ \ sqrt [3] {m / 8} \ le n \ le 3m $ , dh jeder ist polynomisch mit dem anderen verbunden.

---

Ich sehe, dass Sie Ihre Frage überarbeitet haben. Das erklärt, dass ich denke, dass Sie ein Missverständnis haben. Sie sprechen über "Run [Ning] [ein Sat-Solver] auf willkürlichen booleschen Formeln". Sie können jedoch keinen Sat-Solver auf einer willkürlichen booleschen Formel ausführen. Sat-Löser arbeiten nur auf CNF-Formeln.

Wir wissen jedoch, dass jede boolesche Formel auf höchstem Polynom in der Größe der Formel in eine äquisatisierbare CNF-Formel der Größe umgewandelt werden kann, und umgekehrt. Wenn Sie einen Algorithmus hätten, der die Erfüllung von willkürlichen booleschen Formeln in der Zeit Polynome in der Größe der Formel testen könnte, würde dies folgen, dass Sie einen Algorithmus haben, der die Erfüllung von 3CNF-Formeln in der Zeit-Polynom in der Größe der Formel (jeder Die 3CNF-Formel ist eine boolesche Formel) und somit ein Algorithmus, der die Erfüllung von 3CNF-Formeln in der Zeitpolynom in der Anzahl der Variablen testen kann - was den verfügbaren Beweisen widerspricht. Wenn Sie also glauben, dass es keinen Algorithmus gibt, um 3sat in der Zeitpolynom in der Anzahl der Variablen zu lösen, sollten Sie auch glauben, dass es keinen Algorithmus gibt, um die Erfüllung der beliebigen booleschen Formeln in der Zeit Polynom in der Größe der Formel zu testen. < / p>