Siguiente: . Un nivel arriba: Congruencias cuadráticas (CC) Anterior: Residuos cuadráticos en general

Procedimiento de reducción de 3SAT

Sea $\Phi(\mbox{\bf X})=\bigwedge\{c\vert c\in\mbox{\bf C}\}$ una instancia de 3SAT:

• $\mbox{\bf X}=\{X_1,\ldots,X_n\}$ : variables,
• $\mbox{\bf C}$ : cláusulas con 3 literales
  
  $$\forall c\in\mbox{\bf C}\,\exists X_i,X_j,X_k\in\mbox{\bf X},... ... c=X_i^{\epsilon_i}\lor X_j^{\epsilon_j}\lor X_k^{\epsilon_k}.$$
  
  
  Decimos que X_i,X_j,X_k aparecen en c y escribimos $X_i,X_j,X_k\in c$.

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 definamos

$$\begin{array}{rcll} p_j^+ &:=&\sum \{8^i\vert X_j\in c_i\} &... ... donde $X_j$ aparece {\em negada}. \end{minipage}} \end{array}$$

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

$$\begin{eqnarray*}k=0 &:& \\ & & c_0=1 \\ 1\leq k \leq 2m &:& \\ & & c_k=\l... ...q 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^-.$$

Puede verse que 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*}$$

Por último definimos los coeficientes

$$\begin{eqnarray*}F &=& \sum_{k=0}^q t_k \\ D &=& \prod_{k=0}^q P_l^{q+1} \\ ... ...dot(D\mbox{\rm P}^2 + 2\cdot 8^{m+1}\cdot F^2)\mbox{\rm mod }B \end{eqnarray*}$$

Consideramos entonces la instancia del problema (CC) siguiente:

$$T(\Phi): \; \; \mbox{\rm Encontrar $x$ tal que }x^2\equiv A\mbox{\rm mod }B\mbox{\rm\ \ con } 0\leq x \leq F.$$

Siguiente: . Un nivel arriba: Congruencias cuadráticas (CC) Anterior: Residuos cuadráticos en general