Siguiente: Ecuaciones diofantinas cuadráticas (EDC) Un nivel arriba: Procedimiento de reducción de Anterior: Procedimiento de reducción de

.

Veamos que

$$\Phi\mbox{\rm posee una soluci\'on }\Leftrightarrow\;T(\Phi)\mbox{\rm posee una soluci\'on. }$$

1. Si se tiene n variables $X_1,\ldots,X_n$ entonces se puede tener

$$\mbox{\it N3C}={n\choose 3}\cdot 2^3=\frac{4}{3}n(n-1)(n-2)$$

cláusulas de tres literales. Para cada tal cláusula

$$c_{i,j,k}^{\epsilon_i,\epsilon_j\epsilon_k}=X_i^{\epsilon_i}\lor X_j^{\epsilon_j}\lor X_k^{\epsilon_k}$$

y cada asignación $A:\{X_1,\ldots,X_n\}\rightarrow \{0,1\}$ definimos

$$\begin{eqnarray*}r_A(c_{i,j,k}^{\epsilon_i,\epsilon_j\epsilon_k})&=&A(X_i^{\epsi... ...valor verdadero en }c_{i,j,k}^{\epsilon_i,\epsilon_j\epsilon_k} \end{eqnarray*}$$

Naturalmente

$$A(X_i^{\epsilon_i})=\left\{\begin{array}{rl} A(X_i) &\mbox{... ... \\ 1-A(X_i) &\mbox{\rm si }\epsilon_i=0 \end{array}\right.$$

y

$$r_A(c_{i,j,k}^{\epsilon_i,\epsilon_j\epsilon_k})\in\{0,1,2,3\}.$$

2. Dada una instancia $\Phi=\bigwedge \mbox{\bf C}_{\Phi}$ de 3SAT, se tiene que una asignación $A:\{X_1,\ldots,X_n\}\rightarrow \{0,1\}$ satisface a $\Phi$ si y sólo si para toda cláusula c de tres literales se tiene

$$\begin{eqnarray*}c\in \mbox{\bf C}_{\Phi}&\Rightarrow& r_A(c)\geq 1 \\ c\not\in \mbox{\bf C}_{\Phi}&\Rightarrow& r_A(c)\geq 0 \end{eqnarray*}$$

equivalentemente

$$\begin{eqnarray*}c\in \mbox{\bf C}_{\Phi}&\Rightarrow& \exists y_c\in\{0,1,2,3\}... ...{\Phi}&\Rightarrow& \exists y_c\in\{0,1,2,3\}(0=y_c - r_A(c) ) \end{eqnarray*}$$

Si $\{c_i\}_{i=1,\ldots,m}=\mbox{\bf C}_{\Phi}$ es una enumeración de las clásusulas en $\Phi$ definimos

R_A,i(y)=y - r_A(c) + 1.

Por lo anterior,

$$A(\Phi)=1\;\Leftrightarrow \;\forall i\leq m\;\exists y_i\in\{0,1,2,3\}(R_{A,i}(y_i)=0 ).$$

3. Como $\forall A\in\{0,1\}^{[1,m]}, i\leq m, y\in [0,3]:-3\leq R_{A,i}(y)\leq 4$ tenemos

$$\begin{eqnarray*}(\forall i\leq m:\;R_{A,i}(y)=0 ) &\Leftrightarrow& \sum_{i=1}^... ...sum_{i=1}^m R_{A,i}(y)\cdot 8^i \equiv 0\mbox{\rm mod }8^{m+1}. \end{eqnarray*}$$

4. Ahora bien, la función

$$\begin{eqnarray*}\{-1,+1\}\times\{-1,+1\} &\rightarrow& \{0,1,2,3\} \\ (\alpha_1,\alpha_2) &\mapsto& \frac{1}{2}(3-\alpha_1-2\alpha_2) \end{eqnarray*}$$

es una biyección. A cada variable y_i la ``parametrizamos'' por dos variables $(\alpha_{2i-1},\alpha_{2i})$ haciendo

$$y_i=\frac{1}{2}(3-\alpha_{2i-1}-2\alpha_{2i}).$$

De igual manera, la función

$$\begin{eqnarray*}\{-1,+1\} &\rightarrow& \{0,1\} \\ \alpha &\mapsto& \frac{1}{2}(1-\alpha) \end{eqnarray*}$$

es una biyección. A cada valor de verdad A(X_i) lo ``parametrizamos'' por una variable $\alpha_{2m+i}$ haciendo

$$A(X_i)=\frac{1}{2}(1-\alpha_{2m+i}).$$

$\forall i\leq m$ sea $S_i(\vec{\alpha})$ el resultado de sustituir en R_A,i(y_i) las parametrizaciones anteriores. Entonces tenemos

$$\Phi\mbox{\rm es satisfactible }\;\Leftrightarrow \;\exists\v... ...1}^m S_i(\vec{\alpha})\cdot 8^i \equiv 0\mbox{\rm mod }8^{m+1}.$$

5. Introduzcamos la ecuación

$$S_i(\vec{\alpha})=\alpha_0 + 1.$$

Igualmente se tiene

$$\Phi\mbox{\rm es satisfactible }\;\Leftrightarrow \;\exists\v... ...0}^m S_i(\vec{\alpha})\cdot 8^i \equiv 0\mbox{\rm mod }8^{m+1}.$$

6. De acuerdo con los parámetros introducidos en la construcción de $T(\Phi)$ se tiene

$$\begin{eqnarray*}\sum_{i=0}^m S_i(\vec{\alpha})\cdot 8^i \equiv 0\mbox{\rm mod }... ...m_{k=0}^q t_k\alpha_k\equiv \mbox{\rm P}\mbox{\rm mod }8^{m+1} \end{eqnarray*}$$

7. Ahora, se tiene el siguiente Lema: Sean

$$F = \sum_{k=0}^q t_k \mbox{\rm y }D = \prod_{k=0}^q P_l^{q+1}$$

como en el algoritmo. La solución del problema

$$\left\{\begin{array}{ll} (F+x)(F-x)\equiv 0\mbox{\rm mod }D... ...on} \\ 0\leq \vert x\vert \leq F & x\in Z \end{array}\right.$$

es de la forma

$$x=\sum_{k=0}^q t_k\alpha_k\;,\mbox{\rm para alg\'un }\vec{\alpha}\in\{-1,+1\}^{1+q}.$$

8. Así pues, la condición

$$\exists \vec{\alpha}\in\{-1,+1\}^{1+q}:\;\sum_{k=0}^q t_k\alpha_k\equiv \mbox{\rm P}\mbox{\rm mod }8^{m+1}$$

equivale a que exista una solución x del problema

$$\mbox{\it Prob}_1:\left\{\begin{array}{ll} x\equiv \mbox{\r... ...n} \\ 0\leq \vert x\vert \leq F & x\in Z \end{array}\right.$$

9. Por otro lado, se tiene el siguiente Lema: Si p es par y $k\geq 3$ entonces

$$(p+x)(p-x)\equiv 0\mbox{\rm mod }2^{k+1} \;\Leftrightarrow\;\... ... o } \\ (p-x)\equiv 0\mbox{\rm mod }2^{k} \end{array}\right.$$

Con esto resulta que el problema $\mbox{\it Prob}_1$ es equivalente al problema

$$\mbox{\it Prob}_2:\left\{\begin{array}{ll} (\mbox{\rm P}+x)... ...n} \\ 0\leq \vert x\vert \leq F & x\in Z \end{array}\right.$$

10. Conjuntando las dos primeras congruencias del problema $\mbox{\it Prob}_2$ en una sola, vemos que éste equivale al

$$\mbox{\it Prob}_3:\left\{\begin{array}{rl} \left.\begin{arr... ...}) = 1 \end{array}\right\} & x_2,x_3\in Z \end{array}\right.$$

11. Finalmente, tomamos $\lambda_2=\lambda_3=1$ en $\mbox{\it Prob}_3$ y obtenemos

$$(2\cdot 8^{m+1}+D)x^2\equiv (D\mbox{\rm P}^2+2\cdot 8^{m+1}F^2)\mbox{\rm mod }2\cdot 8^{m+1}D,$$

lo cual da propiamente $T(\Phi)$.

12. Conversión de soluciones: $[\mbox{\it Soluci\'on de }\Phi\Rightarrow\mbox{\it Soluci\'on de }T(\Phi)]$: Dada una asignación que satisfaga a $\Phi$ calculamos $\vec{\alpha}$ según las ecuaciones en la observación 4. anterior. La solución de $T(\Phi)$ es

$$x=\sum_{k=0}^q t_k\alpha_k.$$

$[\mbox{\it Soluci\'on de }T(\Phi)\Rightarrow\mbox{\it Soluci\'on de }\Phi]$: Dada una solución x de $T(\Phi)$ localizamos $\vec{\alpha}$ tal que

$$x=\sum_{k=0}^q t_k\alpha_k,$$

y calculamos la asignación que satisface a $\Phi$ según las ecuaciones en la observación 4. anterior. (CC) es pues completo-NP.
Siguiente: Ecuaciones diofantinas cuadráticas (EDC) Un nivel arriba: Procedimiento de reducción de Anterior: Procedimiento de reducción de