Conversión de DNF a CNF: fácil o difícil

En relación con el hilo Probar que la conversión de CNF a DNF es NP-Hard (y un hilo matemático relacionado ):

¿Qué tal la otra dirección, de DNF a CNF? ¿Es fácil o difícil?

En la página 2 de este documento , parecen insinuar que ambas direcciones son igualmente difíciles cuando dicen " Estamos interesados en el aumento de tamaño máximo al cambiar de la representación CNF a la representación DNF (o viceversa) ".

Pero DNF-SAT está en P y CNF-SAT es NP- completo. Así que dada una expresión DNF , debe haber una equisatisfiable CNF expresión cuya longitud es polinomio en la longitud de . Y la se puede hacer en tiempo poli. ¿Es esto correcto? $\phi_1$ $\phi_2$ $\phi_1$ $\phi_1 \to \phi_2$

Editar: se cambió el equivalente a equisatisfiable (es decir, se permiten variables adicionales en ). $\phi_2$

complexity-theory logic satisfiability normal-forms Martin Seymour
fuente

Puede pasar de cualquier fórmula a un CNF que es satisfactoria exactamente cuando la fórmula original está en tiempo polinómico. Es por eso que CNF-SAT es NP-completo. Cualquier instancia SAT (un problema NP-completo) puede reducirse a CNF-SAT en tiempo polinómico. Creo que traducirlo exactamente, no solo preservar la satisfacción siempre dará una explosión exponencial, pero no puedo decirlo con certeza.

Jake

Ver en.wikipedia.org/wiki/Tseitin_transformation . Esencialmente, si permite la introducción de variables auxiliares, puede hacer esta transformación en tiempo polivinílico (aumentando el tamaño de la fórmula como máximo linealmente).

jschnei

Deberá decidir si desea permitir que su conversión introduzca nuevas variables o si la fórmula convertida debe referirse al mismo conjunto de variables (no hay nuevas variables). Este es un punto sutil que tiene un efecto dramático en la respuesta. Entonces, ¿sobre qué quieres preguntar?

@Jake Puede pasar de cualquier fórmula a un CNF equisatisfactable porque CNF-SAT es NP-complete. No es realmente "por qué" CNF-SAT es NP-complete: la prueba habitual de que CNF-SAT es NP-complete no implica traducir fórmulas arbitrarias a CNF; más bien, traduce las máquinas de Turing en fórmulas CNF.

David Richerby

Para DW y para otros, tenía en mente la satisfabilidad . En este sentido, parece que la satisfacción no es más que una reducción (en este caso, a otra fórmula booleana).

Martin Seymour

Respuestas:

Si está dispuesto a introducir variables adicionales, puede convertir de DNF a CNF en tiempo polinomial utilizando la transformación Tseitin . La fórmula CNF resultante será equivalente a la fórmula DNF original: la fórmula CNF será satisfactoria si y solo si la fórmula DNF original fuera satisfactoria. Ver también https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF .

Si no desea permitir la introducción de variables adicionales, la conversión de DNF a CNF es muy difícil. En particular, probar si una fórmula de DNF es una tautología es co-NP-hard. Sin embargo, probar si una fórmula CNF es una tautología se puede hacer en tiempo polinomial (solo verifica por separado si cada cláusula es una tautología, lo cual es fácil ya que cada cláusula es una disyunción de literales). Por lo tanto, si pudiera convertir la forma DNF a la forma CNF en tiempo polinómico, sin introducir nuevas variables, entonces obtendría un algoritmo de tiempo polinómico para probar si una fórmula DNF es una tautología, algo que parece poco probable, dado que esperamos P no es igual a co-NP. O, para decirlo de otra manera, la conversión de DNF a CNF sin introducir variables adicionales es co-NP-hard.

Esta es la diferencia entre equivalencia vs equisatisfabilidad . La equivalencia requiere que las dos fórmulas tengan el mismo conjunto de soluciones (y, por lo tanto, no permite la introducción de variables adicionales). La falta de satisfacción solo requiere que ambas fórmulas sean satisfactorias o ambas no lo sean (y, por lo tanto, permite introducir variables adicionales).

DW
fuente

@Mehrdad, no use comentarios para hacer nuevas preguntas. Tenemos una 'Pregunta' en la esquina superior derecha para si tiene una nueva pregunta que desea hacer. Pero, solo un pequeño consejo ... es posible que desee leer la pregunta en la parte superior de esta página antes de hacer una nueva pregunta ... o, para el caso, publicar este comentario. No puedo evitar notar que has hecho una pregunta donde se encuentra la respuesta en la misma página que tu pregunta.

@DW: Vaya, en realidad vi la otra publicación un poco después y olvidé eliminar mi comentario aquí, lo siento. Lo quitó ahora.

user541686