Um wie viel können wir die Anzahl der Klauseln reduzieren, indem wir von

Wenn wir annehmen, dass wir mit einer Instanz von $k$ -SAT beginnen und versuchen, das Problem in eine Instanz von $(k+m)$ -SAT zu konvertieren, in der es $(k+m)$ Literale pro Klausel gibt, können wir eine Reduzierung der Gesamtzahl der Klauseln?

Nach dem Posten wurde mir klar, dass wir nicht garantieren können, dass die Anzahl der Klauseln reduziert werden kann. Ich frage mich jedoch, ob wir $n$ Klauseln haben, könnten wir so etwas wie $n/k + O(1)$ Klauseln durch eine "Reduktions" -Technik erhalten?

Wenn ja, um wie viel können wir garantieren, dass die Gesamtzahl der Klauseln um reduziert werden kann? Wenn wir zum Beispiel mit $k$ -SAT mit $n_k$ Klauseln beginnen, was ist die kleinste garantierte $n_{k+m}$ , die neue Anzahl von Klauseln, die sich ergibt, wenn wir diese Instanz in $(k+m)$ -SAT konvertieren?

Noch wichtiger ist, wie führen wir diese Konvertierung durch?

Eine Art der Umwandlung ist einfach die Umkehrung der Umwandlung von k-sat in 3-sat:

Denken Sie daran, die Umwandlung von k-sat in "j" -sat, :$j<k$

$$\begin{eqnarray*} && (x_1 \vee x_2 ... \vee x_j \vee ... \vee x_k)\\ \rightarrow && (x_1 \vee x_2 ... x_j \vee d) \wedge (\overline d \vee x_{j+1} \vee x_{j+2} ... x_k)\\ \end{eqnarray*}$$

Hier ist eine Dummy-Variable, was so etwas wie "Diese Klausel ist nicht wahr, aber eine andere Klausel, die ich kenne, ist" bedeutet. Die andere Klausel ist die nächste Klausel, die vom Original abgespalten wurde. Das Obige ist ein Beispiel, in dem 2 j ≥ k ist , andernfalls ist der 2. geteilte Knoten immer noch größer als j , und wir müssen diesen auf die gleiche Weise erneut teilen.$d$$2j \geq k$$j$

Konvertierung rückgängig machen

, dann können Sie die Klauseln kombinieren in:$(x_1 \vee x_2 ... x_j) \wedge (\overline x_j \vee x_{j+1} \vee ... x_k)$

$(x_1 \vee x_2 ... x_{j-1} \vee x_{j+1} \vee x_{j+2} \vee ... x_k)$

Beachten Sie das fehlende in dieser neuen Formel.$x_j$

Natürlich ist es nicht garantiert , dass Sie solche Klauseln in einer beliebigen Formel finden, sodass das kleinste garantierte gleich n k ist .$n_{k+m}$$n_k$

Bei gewöhnlichen Formeln erscheinen jedoch eine Variable und ihre Negation in der Formel. Andernfalls können Sie eine reine wörtliche Eliminierung durchführen ( hier beschrieben ). Nehmen wir der Einfachheit halber auch an, dass . Dann können wir zwei beliebige Klauseln kombinieren, die in einem einen Literal und in dem anderen dessen Negation enthalten. Da jedes Literal eine andere Klausel mit einer Negation haben sollte, kann man empirisch davon ausgehen, dass Sie in der Lage sein sollten, die Anzahl der Klauseln ungefähr zu halbieren (Sie könnten mit einigen Literalen und ihren Negationen in bereits verbundenen Klauseln stecken bleiben, und daher werden Sie mit bleiben einige nicht verbindbare Klauseln am Ende; eine optimale Verbindung solcher Klauseln könnte ein weiteres interessantes Problem sein).$k+m \geq 2k-2$

BEARBEITEN:

Nach dem Nachdenken wurde mir klar, dass darf und nicht an anderer Stelle in der Formel verwendet werden muss, um die beiden Klauseln, zu denen es gehört, zu reduzieren. Daher ist diese Art von Klauseln (eine enthält ein Literal und die andere ihre Negation, wobei dieses Literal an keiner anderen Stelle in der Formel verwendet wird) viel seltener als ich oben gedacht habe. Die eigentliche Antwort lautet also: Es gibt keine Garantie dafür, um wie viel wir die Anzahl der Klauseln in der Formel reduzieren können.$x_j$