FROM 3SAT TO MQ

                                                                        FROM 3SAT TO MQ ( Approche réduite )

La  transformation d’une clause 3SAT en une équation quadratique en passant par les clauses 1IN3SAT et 2IN3SAT  présentée dans From 3SAT TO QP : 3SAT IS P est valide mais on peut aussi réduire le nombre des équations quadratiques et des variables auxiliaires introduites en procédant de la manière suivante :

On se donne un système 3SAT avec n variables et m équations

À chaque clause 3SAT            (X,Y,Z)=1  (1)

On associe l’équation               X*A + Y*B + Z*C=1 (2) dans Z/2Z Ou A B et C sont des nouvelles variables.

 On a :  (1) est valide  ssi (2) admet une solution dans Z/2Z

On a ainsi un système d'équations quadratiques (2) à  m équations et n+ 3m variables.

Pour atteindre le nombre minimum m(m+1) de variables permettant d'appliquer l'algorithme on ajoute des nouvelles variables auxiliaires de la manière suivante :

Si on note (i,j) la variable i présente dans la clause j du système 3SAT

Pour chaque paire (i;j) et (k,l) on introduit une nouvelle variable t et deux nouveaux monômes i*t dans l'équation j et k*t dans l'équation l du système quadratique.

Dans ce processus on privilégie les variables i et j différents si c'est possible jusqu'à atteindre le seuil de m(m+1).

Exemple 1

On se donne le système 3SAT (x,y,z)=1 son MQ équivalent zqt x*a1 + y*a2 + z*a4=1

On a ici m=1 et n= 6 > 1*2 ==> pas de nouvelles variables à ajouter.

Exemple 2 :

On part de 3SAT (x,y,z)=1 , (x,y,t)=1 , (x,z,!t)=1 et (z,!x,t)=1

=> MQ x*a1 + y*a2 + z*a3=1, x*a4 + y*a5 + t*a6=1 ,  x*a7 + z*a8 + t*a9=1 et z*a10 + (1+x)*a11 + t*a12=1

Dans cette phase on a m =4 et n =16 , il manque 4 variables pour atteindre le seuil ,on ajoute les variables a13,a14,a15 et a16 de la manière suivante:

 MQ'

      x*a1 + y*a2 + z*a3 + x*a13 +  y*a14 + z*a15 =1,
      x*a4 + y*a5 + t*a6 +y*a13 + t*a14 + x*a16=1 ,  
      x*a7 + z*a8 + t*a9 + t*a15=1
    et z*a10 + (1+x)*a11 + t*a12 + z*a16=1