Finding Unique Solution to 3SAT Having one solution is P

On notera dans la suite F2 = Z/2Z le corps à deux éléments.

On se donne un système 3SAT ayant une solution unique (S)  et  on se propose de donner algo polynomial pour la trouver.

Ce système est par exemple celui obtenu à partir d’une  factorisation d’un nombre semi-prime  n = p*q  ou p et q sont premiers et p> q.
 

On désigne par n et m les nombres des variables et des équations dans le système (S).

On procède comme dans le lien précèdent, on transforme (S) en un problème MQ ( S’) en ajoutant n1 variables auxiliaires tel que n+n1 > m*(m+1).

On notera dans la suite N=n+n1.

On fait une transformation des variables  ( X1………XN) ===è ( Y1………YN) ou la matrice de changement de variables est inversible triangulaire inferieure qu’on notera T.

On a donc  T(i,ii)=1 pour i=1….N   et T(i,j)=0 si i<j  .

Les autres coefficient de la matrice T sont à déterminer.

On détermine les m premières colonnes de T en faisant disparaitre les termes  Yi*Yj  (i <> j)   après  le remplacement des Xi par les Yi dans le problème MQ ( S’).

Le reste des colonnes de T ( > m ) sont identiques à 1 pour i>j.

 
Le nouveau système MQ ( S’)  peut s’écrire sous la forme condensée.

M(Ym+1……YN)* Transpose(X) = B(Ym+1……..YN).

Ou

M dépend linéairement des Yi , i=m+1….N

B est un vecteur dont les coefficients sont des fonctions quadratiques des Yi , i=m+1 …N

Et transpose le transposé de X = ( Y1…….Ym). qu’on notera Y dans la suite.

Le système  (S) a une solution unique ,le système M*Y = B a au moins une solution.

la matrice T est triangulaire inferieure alors les Yi i=1…n sont déterminés d’une manière univoque à partir des Xi i=1…n .

deux cas sont à distinguer :

    1) n>= m ce cas est peu probable dans un cas d’un système (S) avec une solution unique.
    2) n<m .

On va traiter le cas 2 , le cas 1 peut s’y ramener facilement.

M*Y= B a une ou plusieurs solutions et ces solutions ont en commun les n premières valeurs. M est alors soit inversible soit la sous-matrice (n , N) haute est faite de deux blocs , un inversible ( la partie gauche ) et l’autre identiquement nulle.

Dans le premier cas  on applique directement la  procédure FindInvertibleMatrix  à toute la matrice M

Dans le second cas on résout le sous-système da la partie haute droite et on injecte dans la parie droite à laquelle on applique la procédure FindInvertibleMatrix

Conclusion:

RP = NP 

voir   Np is as (456.84 Ko)