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
Ajouter un commentaire