¿Cuánto podemos reducir el número de cláusulas al convertir de -SAT a -SAT?

Si suponemos que comenzamos con una instancia de -SAT e intentamos convertir el problema en una instancia de -SAT, donde hay literales por cláusula, ¿podemos garantizar una reducción en el cantidad total de cláusulas?$k$$(k+m)$$(k+m)$

Después de publicar me di cuenta de que no podemos garantizar que se pueda reducir el número de cláusulas. Sin embargo, me pregunto si tenemos cláusulas, ¿podríamos obtener algo así como mediante alguna técnica de "reducción"?$n$$n/k + O(1)$

Si es así, ¿en cuánto podemos garantizar que se pueda reducir el número total de cláusulas? Por ejemplo, si comenzamos con -SAT con cláusulas, ¿cuál es la menor cantidad garantizada de , la nueva cantidad de cláusulas, que resultará si convertimos esta instancia a -SAT?$k$$n_k$$n_{k+m}$$(k+m)$

Más importante aún, ¿cómo llevamos a cabo esta conversión?

Un tipo de conversión es simplemente el reverso de la conversión de k-sat-a-3-sat:

Recordemos, la conversión de k-sat a "j" -sat, :$j<k$

Aquí, es una variable ficticia, lo que significa algo así como "Esta cláusula no es verdadera, pero otra que sé que es". La otra cláusula es la siguiente cláusula que se separó del original. Lo anterior es un ejemplo donde , de lo contrario, el segundo nodo dividido seguirá siendo mayor que , y debemos dividirlo nuevamente, de la misma manera.$d$$2j \geq k$$j$

Revertir la conversión

$(x_1 \vee x_2 ... x_j) \wedge (\overline x_j \vee x_{j+1} \vee ... x_k)$ luego puede combinar las cláusulas en:

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

Observe la falta de en esta nueva fórmula.$x_j$

Por supuesto, no se garantiza que encuentre cláusulas como esta en una fórmula arbitraria, por lo que la garantizada más pequeña es igual a .$n_{k+m}$$n_k$

Sin embargo, en fórmulas ordinarias, una variable y su negación aparecerán en la fórmula; de lo contrario, puede realizar la eliminación literal pura (descrita aquí ). Por simplicidad, supongamos también que . Luego podemos combinar dos cláusulas que contengan un literal en una y su negación en la otra. Dado que cada literal debería tener otra cláusula con una negación, uno puede adivinar empíricamente que debería poder reducir a la mitad aproximadamente el número de cláusulas (podría quedar atrapado con algunos literales y sus negaciones en cláusulas ya unidas, y por lo tanto se quedará con algunas cláusulas que no se pueden unir al final; unir óptimamente cláusulas como esta podría ser otro problema interesante$k+m \geq 2k-2$

EDITAR:

Después de reflexionar, me di cuenta de que debe ser libre y no usarse en ninguna otra parte de la fórmula para colapsar las dos cláusulas a las que pertenece. Por lo tanto, este tipo de cláusulas (una que contiene un literal y la otra su negación, ya que este literal no se usa en ninguna otra parte de la fórmula) es mucho más raro de lo que pensaba anteriormente. Entonces, la verdadera respuesta es que no hay garantía de cuánto podemos reducir el número de cláusulas en la fórmula.$x_j$