Probar que la conversión de CNF a DNF es NP-Hard

20

¿Cómo puedo probar que la conversión de CNF a DNF es NP-Hard?

No estoy pidiendo una respuesta, solo algunas sugerencias sobre cómo probarlo.

complexity-theory np-hard satisfiability sat-solvers normal-forms jkjk
fuente
55
Para un análisis en profundidad, eche un vistazo a este documento "Sobre la conversión de CNF a DNF"
Vor
@ A.Schulz: la definición original en el artículo de Steve Cook lo define usando las reducciones de Cook. Parece que esa es la reducción utilizada cuando se discute la dureza NP general en.wikipedia.org/wiki/NP-hard
Kaveh
La conversión CNF <-> DNF no es una decisión, se requiere que sea un idioma. es más una función con entrada y salida y tiene que convertirse en un problema de decisión para preguntar si está en NP, etc. Piense que se ha demostrado que el problema de no decisión conduce a una explosión exponencial en tamaño [por ejemplo, en Vors ref], por lo tanto, un La versión completa de NP del problema de decisión [si hay alguno disponible] es probablemente una simplificación significativa. también como Vors ref muestra la complejidad real de la conversión CNF <-> DNF es un problema de investigación activa ... tenga en cuenta que hay alguna similitud con la eficiencia del algoritmo de compresión ...
vzn
2
@vzn La pregunta pregunta si es NP -duro, no NP -completo. Esto significa que no se requiere ser miembro de NP, por lo que no tiene que ser un problema de decisión.
David Richerby

Respuestas:

18

Informalmente:

En DNF, puede elegir cualquier cláusula para que sea verdadera, para que la fórmula sea verdadera. Esto significa que un DNF que es equivalente a un determinado CNF, es básicamente una enumeración de todas las soluciones a boolean sat en el CNF. Tenga en cuenta que puede haber un número exponencial de soluciones. Dado que la solución de boolean sat para CNF para una solución única es NP-complete, la conversión a DNF esencialmente significa resolver para cada solución. Por lo tanto, es al menos tan difícil como el Boolean SAT y, por lo tanto, es NP-duro.

Ensalada Realz
fuente