Wie viele Klauseln sind erforderlich, wenn sie in CNF-Formeln np-hart sein sollen?

Question

Es ist nicht schwer zu sehen, dass SAT für eine CNF-Formel mit $ N $ Variablen und eine konstante Anzahl von Klauseln in der Polynomzeit gelöst werden kann. Andererseits ist es nicht schwer zu sehen, dass eine CNF-Formel mit $ N $ Variablen und $ O (n) $ -klauseln reicht für NP-Härte (z. B. die Instanzen von SAT, die mit der natürlichen Formel für 3-Färblichkeit verbunden sind, auf planare Grafiken angewendet werden).

wir könnten diese formal als $ \ text {cnfsat} -F- \ text {cnfsat} $ , eine Familie von Problemen, die von einer Funktion $ F $ , in dem Instanzen Formeln in CNF sind, so dass, wenn sie $ N $ Variablen haben, dann auf Die meisten $ F (n) $ -Klauten. Basierend auf diesem, was ich gerne wissen möchte, ist, was ist die kleinste Funktion $ g $ , so dass wir wissen, dass dort vorhanden ist $ f \ in o (g) $ so, dass $ \ text {cnfsat} -F- \ Text {Clauses} $ ist bereits np-hart. Wir wissen, dass G= 1 (konstante Anzahl von Klauseln) nicht funktioniert, und $ g= n $ (lineare Anzahl von Klauseln) funktioniert.

Was ist mit $ g=log n $ ? Gibt es einen einfachen Algorithmus für CNFSAT über Formeln, die $ O (\ lg \ lg n) $ -klauseln haben?

Answer 1

untere gebunden. für $ g \ le c \ cdot \ sqrt {\ \ \ \ \ log n} $ Es gibt einen Polynom-Zeit-Algorithmus . Die Idee ist folgender: Wenn einige Klauseln zu viele Variablen haben, sollte es trivial sein, um einige Variable auszuwählen, um diese Klausel zu erfüllen, ohne die Klauseln mit wenigen Variablen zu verletzen. Wir wiederholen das Folgende:

Die Klausel mit der kleinsten Anzahl von Variablen finden. Sei $ x_1, \ ldots, x_k $ Seien Sie die in dieser Klausel teilnehmenden Variablen.

.
• Wenn $ k> g $ , dann ist die gesamte Formel erfüllt (wir verarbeiten Klauseln nacheinander und wählen eine Variable aus, die wir vorher nicht ausgewählt haben).
• Ansonsten entfernen wir die Klausel. Wir entfernen auch $ X_1, \ LDOs, X_K $ von allen anderen Klauseln.

Nun müssen wir die entfernten Klauseln zufrieden stellen. Da es höchstens $ G $ Clauses gibt, und jeder von ihnen führt in den meisten $ g $ neue Variablen, Es bedeutet, dass es höchstens $ g ^ 2= c ^ 2 \ cdot \ log n $ Variablen insgesamt gibt. Daher gibt es höchstens $ n ^ {c ^ 2} $ variable Kombinationen, und wir können nur rohe-Force verwenden.

bedingte obere Grenze. Es ist in der folgenden Sinne fast fest. annehmen dass die untere Bindung an der SAT mit $ N $ Variablen und $ \ ge c \ CDOT N $ -Kläuse (für einige $ C $ , zB aus $ 3 $ -Coloring ) ist $ \ alpha ^ n $ ( $ \ alpha \ in (1, 2] $ ). Beachten Sie, dass dieselbe untere Grenze nach unserer Transformation hält (da wir es vor jedem Algorithmus auftragen können). Daher gibt es also mindestens $ \ log ^ {1+ \ Epsilon} n $ -Slauten, sie können $ \ frac {\ log ^ {1+ \ Epsilon} n} c $ Variablen und die untere Grenzzeit für die Laufzeit für Unser Problem ist

$$ \ alpha ^ {\ frac {\ log ^ {1+ \ Epsilon} n {1+ \ epsilon} n} c}= n ^ {\ frac {\ log ^ \ epsilon n \ cdot \ log \ alpha} {c}}, $$

das ist super-Polynom.