Resolver el SAT mediante la conversión a la forma normal disyuntiva

Question

El primer conocido $NPC$ problema es el Problema de Satisfacción Booleana, que tiene una prueba de ser $NPC$ hecho por Cook (Teorema de Cook-Levin).

El problema puede describirse fácilmente de la siguiente manera:

En la teoría de la complejidad, el problema de la satisfabilidad (SAT) es un problema de decisión, cuya instancia es una expresión booleana escrita usando sólo AND, OR, NOT, variables y paréntesis. Por lo tanto, debemos dar una respuesta "sí" si hay un conjunto de variables booleanas que dan "TRUE" para lo dado para la expresión correspondiente.

Sin embargo, tengo una pregunta. El artículo de la wikipedia dice lo siguiente:

SAT es más fácil si las fórmulas se limitan a las de forma normal disyuntiva es decir, son disyunción (OR) de términos, donde cada término es una conjunción (AND) de literales (variables posiblemente negadas). Una fórmula de este tipo es realmente satisfactoria si y sólo si al menos uno de sus términos es satisfactorio, y un término es satisfactorio si y sólo si no contiene tanto x como NOT x para alguna variable x. Esto puede comprobarse en tiempo polinómico.

Así que, básicamente, si la expresión se escribe en el DNF, este problema no es $NPC$ sino simplemente $P$ .

Sin embargo, por lo que sé, hay una $O(p(n))$ para transformar cualquier expresión booleana en DNF y DNF existe para cualquier expresión booleana.

¿Qué me estoy perdiendo o interpretando mal? Obviamente hay un error en mi lógica, porque resultó en hacer el problema del SAT $P$ pero no $NP$ .

Gracias.

Answer 1

Tu afirmación de que puedes convertir una fórmula arbitraria a DNF en tiempo polinómico es errónea.

Se puede convertir una fórmula booleana en DNF, pero la fórmula resultante puede ser mucho más grande que la fórmula original, de hecho, exponencialmente. Dado que el algoritmo de conversión debe, como mínimo, escribir la fórmula DNF resultante, su tiempo de ejecución debe ser al menos la longitud de la salida y, por tanto, su tiempo de ejecución en el peor de los casos debe ser exponencial.

Incluso si de alguna manera se suaviza la cuestión de escribir la versión DNF de la fórmula de entrada, el algoritmo que propones toma una fórmula de tamaño $x$ lo convierte en una fórmula DNF del tamaño del peor caso $2^x$ y luego calcula la satisfacción de la fórmula DNF en tiempo $P(2^x)$ para algún polinomio $P$ . En general, esto no es mejor que intentar todas las asignaciones satisfactorias posibles en la fórmula original.

El artículo de Wikipedia sobre la "Forma Normal Disyuntiva" tiene un ejemplo de una fórmula que explota cuando se convierte en DNF. Pero es un ejemplo fácil. Considera:

$$(A_1\lor B_1)\land(A_2\lor B_2)\land\cdots\land(A_n\lor B_n)$$

Esta tiene una longitud proporcional a $n$ . Pero en DNF se convierte en:

$$(A_1\land A_2\land\cdots\land A_n)\lor\\ (B_1\land A_2\land\cdots\land A_n) \lor \\ (A_1\land B_2\land\cdots\land A_n) \lor \\ (B_1\land B_2\land\cdots\land A_n) \lor \\ \vdots\\ (B_1\land B_2\land\cdots\land B_n)\hphantom{\lor} $$

con $2^n$ cláusulas.