Siguiente: Algunos problemas principales completos-NP Un nivel arriba: Completitud-NP Anterior: El primer problema completo-NP

Otros problemas completos-NP en formas proposicionales

Problema SAT-FNC

Consiste en decidir si acaso una forma proposicional dada como una forma conjuntiva es satisfactible.

Formalmente el problema se especifica como sigue:


Instancia:

Solución:

Proposición 4.1   SAT-FNC es completo-NP.

Para esto veamos que SAT se reduce a SAT-FNC.

Lema 4.1   Existe un traductor logarítmico

$$\begin{eqnarray*}\mbox{\it FC}:\{\mbox{\rm Formas proposicionales}\} &\rightarro... ...m Formas conjuntivas}\} \\ \phi &\mapsto& \mbox{\it FC}(\phi) \end{eqnarray*}$$

de manera que $\forall \phi$: $\phi$ es satisfactible cuando y sólo cuando $\mbox{\it FC}(\phi)$ también lo sea.

De hecho, tendremos que una asignación $\mbox{\boldmath$\epsilon$ }$ satisface a $\phi$ si y sólo si una extensión de $\mbox{\boldmath$\epsilon$ }$ satisface a $\mbox{\it FC}(\phi)$. Demostración: Presentamos a grandes rasgos reglas de transformación para calcular $\mbox{\it FC}(\phi)$ a partir de $\phi$.

1.

Aplicar negaciones al nivel más bajo:

$$\begin{eqnarray*}\neg(\phi \land \psi) &\leadsto& \neg(\phi)\lor\neg(\psi) \\ ... ...to& \neg(\phi)\land\neg(\psi) \\ \neg\neg\phi &\leadsto& \phi \end{eqnarray*}$$

Reiterando las dos primeras reglas y luego aplicando la tercera en cada variable, toda fórmula proposicional se transforma en una expresión formada a partir de literales utilizando conjunciones y disyunciones. Llamemos a éstas formas y/o. Las primeras dos reglas se realizan mediante un procedimiento similar al reconocimiento de cadenas equilibradas de paréntesis. Utilizando contadores para referirse a las posiciones de los paréntesis se las puede realizar en espacio logarítmico. La tercera regla se aplica directamente mediante un revisor de paridades de cadenas de ``$\neg$'''s consecutivos.

2.

Cálculo de formas conjuntivas: Definimos el operador $\Phi:\{\mbox{\rm Formas y/o}\}\rightarrow \{\mbox{\rm Formas conjuntivas}\}$ de manera inductiva como sigue:

$$\begin{eqnarray*}\phi\mbox{\rm literal} &\Rightarrow& \Phi(\phi)=\phi \\ \left... ...\right] \land \bigwedge_{i_2}\left[\neg Y\lor F_{2,i_2}\right] \end{eqnarray*}$$

donde Y, en la última relación, es una nueva variable. Estas transformaciones son también susceptibles de realizarse en espacio logarítmico.

Una forma conjuntiva-3, FC-3, es una forma conjuntiva tal que toda cláusula en ella consta de exactamente 3 literales.

Problema 3-SAT

Consiste en decidir si acaso una FC-3 dada es satisfactible.

Formalmente el problema se especifica como sigue:


Instancia:

Solución:

Proposición 4.2   3-SAT es completo-NP.

Para esto veamos que SAT-FNC se reduce a 3-SAT.

Lema 4.2   Existe un traductor logarítmico

$$\begin{eqnarray*}\mbox{\it FC}:\{\mbox{\rm Formas conjuntivas}\} &\rightarrow& \{\mbox{\rm FC-3's}\} \\ \phi &\mapsto& \mbox{\it FC}(\phi) \end{eqnarray*}$$

de manera que $\forall \phi$: $\phi$ es satisfactible cuando y sólo cuando $\mbox{\it FC}(\phi)$ también lo sea.

De hecho, tendremos que una asignación $\mbox{\boldmath$\epsilon$ }$ satisface a $\phi$ si y sólo si una extensión de $\mbox{\boldmath$\epsilon$ }$ satisface a $\mbox{\it FC}(\phi)$. Demostración: Si $\mbox{\it Fr}=L_1\lor L_2\lor L_3$ es una frase 3 literales hagamos $\mbox{\it FC}(\mbox{\it Fr})=\mbox{\it Fr}$. Si $\mbox{\it Fr}=L_1\lor L_2\lor \cdots \lor L_k$ es una frase con k> 3 literales consideremos k-3 nuevas variables $Y_1,\ldots,Y_{k-3}$ y hagamos

$$\mbox{\it FC}(\mbox{\it Fr})=\left\{\begin{array}{rlclcllc} ... ...& \neg Y_{k-3} &\lor& L_{k-1}&\lor& L_k &)& \end{array}\right.$$

Es claro que una asignación satisface $\mbox{\it Fr}$ si y sólo si una extensión de ella satisface $\mbox{\it FC}(\mbox{\it Fr})$. Sea ahora $\phi=\bigwedge_i\mbox{\it Fr}_i$ una FC. Podemos suponer que toda cláusula en $\phi$ consta de al menos tres literales (si no fuera así podemos repetir una literal pues la disyunción es una operación equipotente). Hagamos $\mbox{\it FC}(\phi)=\bigwedge_i\mbox{\it FC}(\mbox{\it Fr}_i)$. Entonces $\mbox{\it FC}(\phi)$ es del tipo 3-FNC y será satisfactible si y sólo si $\phi$ lo es.
Siguiente: Algunos problemas principales completos-NP Un nivel arriba: Completitud-NP Anterior: El primer problema completo-NP