Siguiente: . Un nivel arriba: Ecuaciones diofantinas cuadráticas (EDC) Anterior: .

Procedimiento de reducción de 3SAT

El siguiente procedimiento es similar al anterior. Sea $\Phi(\mbox{\bf X})=\bigwedge\{c\vert c\in\mbox{\bf C}\}$ una instancia de 3SAT de m cláusula y n variables. Supondremos que $\Phi$ no posee cláusulas repetidas ni tautologías. Enumeremos al conjunto de clásusulas como

$$\mbox{\bf C}_{\Phi}=\{c_1,\ldots,c_m\}.$$

Hagamos

$$\mbox{\rm PC}=-\sum_{i=1}^m 8^i=\frac{8}{7}(8^m-1),$$

y para cada variable X_j

$$\begin{array}{cc} p_j^+ :=\sum \{8^i\vert X_j\in c_i\} & p_j^- :=\sum \{8^i\vert\neg X_j\in c_i\} \end{array}$$

Sea q=2m+n. Para cada $k\in [0,q]$ definimos:

$$\begin{eqnarray*}k=0 &:& c_0=1 \\ 1\leq k \leq 2m &:& c_k=\left\{\begin{array}... ... 2m+1\leq k \leq q&:& c_k=\frac{1}{2}(p_{k-2m}^+ - p_{k-2m}^-) \end{eqnarray*}$$

Hagamos

$$\mbox{\rm P}=\mbox{\rm PC} + \sum_{k=0}^q c_k + \sum_{j=1}^n p_j^-.$$

Existen 1+q coeficientes

$$\alpha_0,\alpha_1,\ldots,\alpha_q\in\{-1,+1\}$$

tales que

$$\mbox{\rm P}=\sum_{k=0}^q c_k\alpha_k .$$

Tomemos los q primos consecutivos $P_0,P_1,\ldots,P_q$ a partir de P₀=13. Para cada $k\in [0,q]$ elegimos $t_k\in N$ como el mínimo entero que satisface el sistema de congruencias

$$\begin{eqnarray*}t_k &\equiv& c_k\mbox{\rm mod }8^{m+1} \\ t_k &\equiv& 0\mbox... ...kslash {k}}P_l^{q+1} \\ t_k &\not\equiv& 0\mbox{\rm mod }P_k \end{eqnarray*}$$

Definimos los coeficientes

$$\begin{eqnarray*}F &=& \sum_{k=0}^q t_k \\ D &=& \prod_{k=0}^q P_l^{q+1} \\ ... ...& -2\cdot 8^{m+1}\cdot D \\ A &=& (D+1)^3 2\cdot 8^{m+1} + D \end{eqnarray*}$$

Consideramos entonces la instancia del problema (EC) siguiente:

$$T(\Phi): \; \; \mbox{\rm Encontrar $x_1,x_2$ tales que }Ax_1^2+Bx_2-C=0.$$