El primer problema completo-NP

Siguiente: Otros problemas completos-NP en Un nivel arriba: Formas proposicionales y el Anterior: Formas booleanas

El primer problema completo-NP

Problema SAT: Consiste en decidir si acaso una forma proposicional dada es satisfactible.

Formalmente el problema se especifica como sigue:

Instancia:
$\begin{pagi}{34}Una forma proposicional $F$ .\end{pagi}$
Solución:
$\begin{pagi}{34}$\left\{\begin{array}{ll} 1 &\mbox{\rm si $F$\space es satisfac... ... 0 &\mbox{\rm si $F$\space es insatisfactible.} \end{array}\right.$\end{pagi}$

Toda instancia $F(X_1,\ldots,X_{n_0})$ de SAT puede verse como una palabra sobre el alfabeto

$\begin{displaymath}\mbox{\it AlfProp}_{n_0}=\{(,),\neg,\land,\lor,\mbox{\bf0},\mbox{\bf 1}\}\cup\mbox{\bf X},\end{displaymath}$

de n₀+7 símbolos. Si la longitud de esta palabra es n tenemos que

1.

hay a lo sumo $\left\lceil\frac{n}{2}\right\rceil$ apariciones de variables,

2.

la cadena se codifica como una palabra de longitud $O(n\log n)$ sobre el alfabeto $\{0,1\}$ . En efecto,

(a)

a cada variable X_j la codificamos por la palabra formada por un símbolo x seguido de la representación de j en base 2. Digamos, $X_5\leftrightarrow x101$ .

(b)

codifiquemos a cada uno de los símbolos en uso actual como se indica en la Tabla 7.1.

Table 7.1: Codificación de símbolos.

Símbolo	Código	Símbolo	Código
(	1	$\mbox{\bf0}$	110
)	10	$\mbox{\bf 1}$	111
$\neg$	11	x	1000
$\land$	100	0	1001
$\lor$	101	1	1010

(c)

cada cadena en el lenguaje proposicional se transcribe como una cadena de cadenas de 0's y 1's. V.gr,:

$\begin{displaymath}\neg(X_1\land X_5)\leftrightarrow[11,1,1000,1010,100,1000,1010,1001,1010].\end{displaymath}$

(d)

A una cadena de cadenas de 0's y 1's. la representamos, mediante una sola cadena de 0's y 1's, cambiando cada 1 por 10, cada 0 por 0 mismo y cada ``,'' por 11. V.gr,:

$\begin{displaymath}\begin{array}{cc} [11,1,1000,1010,100,1000,1010,1001,1010] \... ...0 11\ 10000\ 11\ 100100\ 11\ 100010\ 11\ 100100 \end{array}\end{displaymath}$

3.

Consecuentemente, respecto a reducciones en espacio logarítmico es irrelevante utilizar el alfabeto $\mbox{\it AlfProp}_{n_0}$ o el alfabeto $\{0,1\}$ pues

$\begin{displaymath}\log(n\log n)\leq 2 \log n.\end{displaymath}$

Lo mismo vale respecto a reducciones polinomiales.

Teorema 3.1 (Cook, 1971) SAT es completo-NP.

Demostración: Veamos primeramente que $\mbox{\rm SAT}\in\mbox{\rm NP}$ . Dada una instancia $F=F(X_1,\ldots,X_{n_0})$ , se genera una asignación $\mbox{\boldmath$\epsilon$ }\in\mbox{\rm Dos}^n$ de manera no determinista. La evaluación de F sobre $\mbox{\boldmath$\epsilon$ }$ requiere un tiempo proporcional al número de conectivos que aparecen en F el cual está limitado por la propia longitud de F. Veamos ahora que $\mbox{\rm SAT}$ es difícil- $\mbox{\rm NP}$ . Para esto, hay que ver que cualquier problema en NP se reduce a SAT, para lo cual veremos que para cualquier máquina de Turing no-determinista M, acotada en tiempo por un polinomio p(n), podemos construir un traductor logarítmico

$\begin{eqnarray*}T_M:\{\mbox{\rm Entradas de $M$ }\} &\rightarrow& \{\mbox{\rm F... ...posicionales}\} \\ \mbox{\bf x} &\mapsto& \phi_{\mbox{\bf x}} \end{eqnarray*}$

de manera que $\forall \mbox{\bf x}:\ M(\mbox{\bf x})\downarrow\ \Leftrightarrow\ \mbox{\rm SAT}(\phi_{\mbox{\bf x}})=\mbox{\it S\'\i}.$ Consideremos una computación terminal en M, correspondiente a una entrada $\mbox{\bf x}$ de longitud n. Esta es una sucesión finita de descripciones instantáneas cuya longitud es O(p(n)). Escribámosla $\mbox{\it Comp}(\mbox{\bf x})=\bullet\mbox{\it di}_0\bullet\mbox{\it di}_1\cdots\bullet\mbox{\it di}_{p(n)}.$ Cada $\mbox{\it di}_i=[\mbox{\bf x}_iq_ia_i\mbox{\bf y}_i]$ involucra del orden de p(n) símbolos. De hecho, podemos confundir a la pareja q_ia_i como un solo símbolo (nuevo) q_ia_im_i, donde m_i indica al movimiento que hace M estando en el estado q_i y encontrando el símbolo a_i. Así, se puede escribir la computación $\mbox{\it Comp}(\mbox{\bf x})$ como una palabra de longitud (p(n)+1)² sobre un cierto alfabeto A'. Consideremos el conjunto de variables proposicionales $\mbox{\it VP}=\left\{X_{ia}\vert\leq i\leq (p(n)+1)^2-1, a\in A'\right\}.$ La intención de cada una de estas variables es

$\begin{displaymath}X_{ia}\mbox{\rm es verdadero}:\mbox{\rm\begin{minipage}[t]{30... ...sici\'on $i$ de $\mbox{\it Comp}(\mbox{\bf x})$.\end{minipage}}\end{displaymath}$

La construcción de $\phi_{\mbox{\bf x}}\in\mbox{\it FormProp}(\mbox{\it VP})$ se hará teniendo en mente lo siguiente:

1.: Para cada i existe un único a tal que X_ia es verdadero.
2.: La descripción inicial $\mbox{\it di}_0$ es de la forma $q_0\mbox{\bf x}$ .
3.: La última descripción $\mbox{\it di}_{p(n)}$ es terminal.
4.: Cada descripción $\mbox{\it di}_{i+1}$ se sigue de su anterior $\mbox{\it di}_{i}$ según las transiciones de la máquina M.

De acuerdo con el punto 1 anterior definamos

$\begin{displaymath}\phi_{1,\mbox{\bf x}}=\bigwedge_{i}\left[\bigvee_{a}\left(X_{ia}\land\bigwedge_{b\not=a}\neg X_{ib}\right)\right]. \end{displaymath}$

(16)

De acuerdo con el punto 2 anterior consideremos lo siguiente:

La descripción inicial $\mbox{\it di}_0$ , como cualquier otra, va entre dos `` $\bullet$ '''s. Sea

$\begin{displaymath}\phi_{2,1,\mbox{\bf x}}=X_{0\bullet}\land X_{(p(n)+1),\bullet}. \end{displaymath}$ (17)
El primer símbolo de $\mbox{\it di}_0$ corresponde al símbolo compuesto formado por el estado inicial q₀ de M y el símbolo inicial x₁ de $\mbox{\bf x}$ . Sea

$\begin{displaymath}\phi_{2,2,\mbox{\bf x}}=\bigvee_{[q_0x_1m]\in\mbox{\rm Transiciones en $M$ }}X_{1[q_0x_1m]}. \end{displaymath}$ (18)
Los siguientes n-1 símbolos de $\mbox{\it di}_0$ corresponden a los símbolos x_i que conforman a $\mbox{\bf x}$ . Sea

$\begin{displaymath}\phi_{2,3,\mbox{\bf x}}=\bigwedge_{i=2}^nX_{ix_i}. \end{displaymath}$ (19)
El resto de $\mbox{\it di}_0$ se llena con blancos. Sea

$\begin{displaymath}\phi_{2,4,\mbox{\bf x}}=\bigwedge_{i=n+1}^{p(n)}X_{i\Box}. \end{displaymath}$ (20)

Tomemos pues a la conjunción de las fórmulas en las ecuaciones 7.2-7.5:

$\begin{displaymath}\phi_{2,\mbox{\bf x}}=\phi_{2,1,\mbox{\bf x}}\land\phi_{2,2,\... ...x}}\land\phi_{2,3,\mbox{\bf x}}\land\phi_{2,4,\mbox{\bf x}}. \end{displaymath}$

(21)

De acuerdo con el punto 3 anterior definamos

$\begin{displaymath}\phi_{3,\mbox{\bf x}}=\bigvee_{i=p(n)(p(n)+1)+1}^{(p(n)+1)^2-... ...in&\mbox{\rm Transiciones}\end{array} }X_{i[q_Fam]}\right]. \end{displaymath}$

(22)

Finalmente, para expresar la necesidad de que dos descripciones contiguas $\mbox{\it di}_{i}$ y $\mbox{\it di}_{i+1}$ se ajustan a las transiciones de M, observamos que tales dos descripciones han de coincidir en todas partes salvo en las posiciones vecinas a los símbolos compuestos correspondientes a estados. Definamos entonces un predicado $\Phi(a_1,a_2,a_3,a_4;j)$ tal que

$\begin{displaymath}\begin{array}{rcl} \Phi(a_1,a_2,a_3,a_4;j) &\Leftrightarrow&... ...or \ \left((a_2=\bullet)\land(a_4=\bullet)\right) % \end{array}\end{displaymath}$

Con $\Phi$ podemos simular efectivamente las transiciones de M. Sea entonces

$\begin{displaymath}\phi_{4,\mbox{\bf x}}=\bigwedge_{j=1}^{p(n)(p(n)+1)}\bigvee_{... ...(j),a_2}\land X_{(j+1),a_3}\land X_{(p(n)+j),a_4} \right]. \end{displaymath}$

(23)

La forma proposicional a construir es entonces la conjunción de las fórmulas 7.1, 7.6, 7.7 y 7.8:

$\begin{displaymath}\phi_{\mbox{\bf x}}=\phi_{1,\mbox{\bf x}}\land \phi_{2,\mbox{\bf x}}\land \phi_{3,\mbox{\bf x}}\land \phi_{4,\mbox{\bf x}}. \end{displaymath}$

(24)

De su misma construcción tenemos que toda computación terminal, con inicio en $\mbox{\bf x}$ , determina una asignación que satisface a la fórmula $\phi_{\mbox{\bf x}}$ y, viceversa, toda asignación que satisfaga a esta fórmula determina también a una computación terminal a partir de $\mbox{\bf x}$ .

Siguiente: Otros problemas completos-NP en Un nivel arriba: Formas proposicionales y el Anterior: Formas booleanas

Guillermo Morales-Luna
2000-07-10