El punto de 3CNF es que es una "forma normal" para las fórmulas: como usted menciona, cada fórmula es equivalente, hasta una ampliación cuadrática (¿lineal?), a una fórmula 3CNF. Las fórmulas 3CNF son "simples" y, por tanto, más fáciles de tratar. En particular, si alguna vez lees sobre la completitud NP, te darás cuenta de que queremos poner nuestros "problemas desafiantes" en una forma tan simple como sea posible. Esto facilita tanto el diseño y el análisis de los algoritmos que resuelven estos problemas, como demostrar que otros problemas también son difíciles reduciendo 3CNF a ellos (mostrando cómo resolver 3CNF usando un algoritmo para ellos).
Nos preocupamos específicamente por 3CNF por razones históricas, fue el primer (o uno de los primeros) problemas NP-completos (consulte el artículo de Cook o el de Karp en sus respectivas páginas). Además, 2CNF no es "completo" (las fórmulas arbitrarias no pueden ser equivalentes a un 2CNF), y es fácil determinar si son satisfacibles o no (busque en Google si está interesado).
La conversión de CNF a 3CNF se explica mejor con un ejemplo. Convertimos cada cláusula por separado. La cláusula $A \lor B \lor C \lor D \lor E$ es equivalente al 3CNF $$(A \lor B \lor x_1) \land (\lnot x_1 \lor C \lor x_2) \land (\lnot x_2 \lor D \lor E), $$ en el sentido de que la fórmula original (en este caso, una sola cláusula) es satisfactoria si la fórmula convertida lo es. Se convierte cada una de las cláusulas y se toma su conjunción.
Suponga que tiene una fórmula arbitraria que utiliza las conectivas $\lnot,\lor,\land$ . Imagínatelo como un árbol, en el que los nodos interiores están etiquetados con $\lnot,\lor,\land$ y cada nodo tiene una ( $\lnot$ ) o dos ( $\lor,\land$ ) niños. Lamento no poder proporcionar una imagen. El primer paso es "empujar las negaciones a las hojas" utilizando las reglas de de Morgan (q.v.). Eso nos libra de todas las $\lnot$ nodos, pero ahora las hojas pueden ser literales (variables o negaciones de variables). Ahora convertimos la fórmula en una CNF de forma recursiva.
Denota por $\varphi$ la función que estamos construyendo, que toma una fórmula como la anterior (con $\land,\lor$ y posiblemente variables negadas) y devuelve un CNF. Para el caso base, tenemos $\varphi(x) = x$ y $\varphi(\lnot x) = \lnot x$ . Para una fórmula de la forma $A \land B$ no tenemos que trabajar mucho: definimos $\varphi(A \land B) = \varphi(A) \land \varphi(B)$ . El caso más difícil son las fórmulas de la forma $A \lor B$ Una opción algo más económica es $$\varphi(A \lor B) = (y \lor \varphi(A)) \land ((\lnot y) \lor \varphi(B)), $$ donde $y$ es una nueva variable, y $y \lor \varphi(A)$ significa añadir $y$ a todas las cláusulas.
Las fórmulas generales con conectivos arbitrarios pueden manejarse expresando los conectivos mediante $\lor,\land,\lnot$ por ejemplo, escribiendo una tabla de verdad; sin embargo, esto puede ser bastante derrochador.
Toda la construcción da lugar a un aumento cuadrático del tamaño de la fórmula (sus "ocurrencias de variables"; hay muchas otras formas de definir el tamaño de la fórmula). Sin embargo, el resultado que citas es sólo una ampliación lineal (de hecho, por un factor de $24$ ). Es muy posible que esa construcción exista, pero yo no la conozco; quizás alguno de los lectores sí. La parte de SAT a 3SAT tiene una ampliación lineal con un factor de $3$ .
Si no permite añadir nuevas variables, entonces no es posible una conversión sencilla. Aunque siempre es posible convertir una fórmula arbitraria en una CNF (utilizando el enfoque de la "tabla de verdad"), no todas las fórmulas son convertibles en una 3CNF sin añadir nuevas variables. Un ejemplo es la paridad en $4$ variables. Además, la conversión de una fórmula arbitraria a una CNF puede dar lugar a una explosión exponencial, por ejemplo para la paridad en $n$ variables pasamos de $\Theta(n^2)$ a $\Theta(n2^n)$ .
0 votos
El límite propuesto para el tamaño de la fórmula depende del tipo de fórmula que se admita como entrada. Si se permite, por ejemplo, el operador de equivalencia $\leftrightarrow$ se obtiene una explosión exponencial.