next up previous contents
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: Supondremos que $\Phi$ no posee cláusulas repetidas ni tautologías. Enumeremos al conjunto de clásusulas como

\begin{displaymath}\mbox{\bf C}_{\Phi}=\{c_1,\ldots,c_m\}.\end{displaymath}

Hagamos

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

y para cada variable Xj definamos

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

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

\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

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

Puede verse que existen 1+q coeficientes

\begin{displaymath}\alpha_0,\alpha_1,\ldots,\alpha_q\in\{-1,+1\}\end{displaymath}

tales que

\begin{displaymath}\mbox{\rm P}=\sum_{k=0}^q c_k\alpha_k .\end{displaymath}

Tomemos los q primos consecutivos $P_0,P_1,\ldots,P_q$ a partir de P0=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:

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



 
next up previous contents
Siguiente: . Un nivel arriba: Congruencias cuadráticas (CC) Anterior: Residuos cuadráticos en general
Guillermo Morales-Luna
2000-07-10