Siguiente: .
Un nivel arriba: Congruencias cuadráticas (CC)
Anterior: Residuos cuadráticos en general
Sea
una instancia de 3SAT:
-
: variables,
-
: cláusulas con 3 literales
Decimos que
Xi,Xj,Xk aparecen en c y escribimos
.
Supondremos que
no posee cláusulas repetidas ni tautologías.
Enumeremos al conjunto de clásusulas como
Hagamos
y para cada variable Xj definamos
Sea q=2m+n. Para
definimos un coeficiente ck:
Hagamos
Puede verse que existen 1+q coeficientes
tales que
Tomemos los q primos consecutivos
a partir de P0=13.
Para cada
elegimos
como el mínimo entero que satisface el sistema de congruencias
Por último definimos los coeficientes
Consideramos entonces la instancia del problema (CC) siguiente:
Siguiente: .
Un nivel arriba: Congruencias cuadráticas (CC)
Anterior: Residuos cuadráticos en general
Guillermo Morales-Luna
2000-07-10