SAT es en P si hay muchas cláusulas de manera exponencial en el número de variables?

Question

defino un larga CNF para contener al menos $ 2 ^ \ frac {n} {2} $ cláusulas, donde $ n $ es el número de sus variables. Deje $ \ text {long-SAT} = \ {\ phi: \ phi $ es un satisfiable largo CNF fórmula $ \} $.

Me gustaría saber por qué $ \ text {long-SAT} \ in P $. Primero pensé que es $ \ texto {} $ APN ya que puedo hacer una transformación polinómica de $ \ text {SAT} $ a $ \ text {long-SAT} $, ¿no?

Pero tal vez pueda reducir $ \ texto {2-SAT} $ a $ \ text {long-SAT} $? ¿Cómo lo hago?

Answer 1

A menos que me falta algo, es trivialmente en P como la longitud de la fórmula es exponencial en el número de variables. Por lo tanto todos los $ 2 ^ {n} $ asignaciones de verdad pueden ser generados y se comprueban en tiempo polinómico en la longitud de la fórmula.

Answer 2

En este caso, la respuesta es trivial como puntos a Luke . Sin embargo, a medida que parecen tener llegar a la definición sí mismo, tenga en cuenta esto.

Para SAT, denominadas transiciones de fase con respecto a la relación de recuento variable para recuento cláusula se han observado [1,2]. Si es pequeño, los casos son fáciles y difíciles si es grande. Parece que hay una transición más o menos nítida de fácil a difícil. Esta parece ser una investigación. cstheory.SE tiene algo más en este fenómeno.

Por lo tanto, si se ajusta a su definición de "larga" a polinómica La explosión, es posible que de hecho tener una clase no trivialmente fácil - es decir, en el P - sólo porque usted tiene mucho más cláusulas que variables.

---

1. El SAT fase de transición a través de IP Gent (1994 )
2. La determinación de la complejidad computacional de característicos 'transiciones de fase' por R . Monasson, R. Zecchina et al. (1999)