Siguiente: Divisibilidad simultánea de polinomios 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. 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, de acuerdo con la Observación 10. de CC el problema $\mbox{\it Prob}_3$ posee una solución.

2. Tomamos

$$\begin{eqnarray*}\lambda_2 &=& (D+1)^3 \\ \lambda_3 &=& -1 \end{eqnarray*}$$

en $\mbox{\it Prob}_3$. Estos valores cumplen con la tercera condición del $\mbox{\it Prob}_3$. La primera ecuación es equivalente a que para algún x₂ se tenga

$$(D+1)^3 2\cdot 8^{m+1}\cdot (F^2 -x_1^2) +D(x_1^2-\mbox{\rm P}^2)= 2\cdot 8^{m+1}\cdot F\cdot x_2.$$

En cuanto a la segunda condición tenemos la equivalencia

$$(D+1)^3 2\cdot 8^{m+1}\cdot (F^2 -x_1^2) +D(x_1^2-\mbox{\rm P}^2)\geq 0\;\Leftrightarrow\; 0\leq x_1\leq F.$$

Así pues la satisfactibilidad de $\Phi$, equivalente a la solubildad del $\mbox{\it Prob}_3$, es equivalente a la solubildad en N de la ecuación

$$(D+1)^3 2\cdot 8^{m+1}\cdot (F^2 -x_1^2) +D(x_1^2-\mbox{\rm P}^2)-x_2 2\cdot 8^{m+1}\cdot F=0,$$

la cual equivale a $T(\Phi)$.

3. Conversión de soluciones: La conversión de soluciones se hace exactamente igual que en CC.