CNF a DNF - la conversión es NP Hard

Question

¿Cómo puedo demostrar que la conversión de CNF a DNF es NP-Difícil? No estoy pidiendo una respuesta, sólo algunas sugerencias sobre cómo ir a probarlo.

Answer 1

Después de convertir una fórmula CNF a DNF puedo resolver el problema NP-completo SAT en tiempo lineal comprobando cada cláusula DNF hasta encontrar una que no contenga un literal y su negación. Esto significa que SAT es reducible en tiempo polinómico de Turing a la conversión de CNF a DNF. La existencia de tal reducción es la definición de dureza NP.

Answer 2

Tanto la pregunta como la otra respuesta de KJ parecen suponer que la conversión CNF ←→ DNF puede hacerse en el espacio P, lo cual no es el caso. [no estoy seguro de cuál en este momento] [sugiero migrar esta pregunta a cs.se para un mejor análisis allí].