SAT Solver (P=NP)

                                                                         Wild El Khadra ( wildelkhadra@gmx.fr)

 

 

Abstract. We describe a new algorithm to solve a 3SAT problem. We firstly define the 2In3Sat problem, show that it’s NP-complet then present the new algorithm used to solve it The algorithm is  based on a new way to encode 2In3SAT on a system of underdetermined system of multivariate quadratic equations over  finite field with even characteristic.

 

KeyWords :3SAT , 1In3SAT, 2In3SAT , underdetermined system ,multivariate equations , even characteristic ,polynomial complexity.

 

1)  Introduction:

 

L’objectif  de cette étude est de présenter un algorithme pour résoudre le problème 3SAT  et une implémentation en c#  de ce algorithme.

On notera dans la suite !X la variable opposée à X .
On utilisera dans la suite d’une manière indifferente  1 ou True pour la valeur logique positive et 0 ou False pour la valeur négative.

On notera les clauses d’un système 3SAT   (x,y,z) =1.

Un clause est dite positive si toutes ses variables sont positives et négative si toutes ses variables sont négatives.

On sait que 3SAT et 1In3Sat sont NP-complet.

On sait aussi que la question de la résolution d'un système d'équations quadratiques (QP) est NP-complet dans Z/2Z  en général mais admet une solution polynomiale si n > m(m+1)/2 ou n est le nombre des variables et m le nombre des équations.Ce type de problème QP est dit problème QP sous-déterminé.

 

Un problème QP sous-déterminé sera noté dans la suite QPSD.

 

L'approche qu’on va présenter est de partir d'une instance d'un problème 3SAT et de la transformer en une instance d'un problème QPSD.

Pour cela on procède en trois étapes :

 

a) Transformer une système 3SAT (1) en un autre problème 1In3SAT (2) qui est valide ssi le système (1) est valide.

b)  Transformer 1in3SAT (2) en un problème 2In3SAT.

c) Transformer le problème 2In3SAT en un problème QPSD.

 

2) Algorithme .

Si on considère une instance d'un problème 3SAT.

Si aucune clause n'est positive ou aucune clause n'est négative alors le système est valide. Il suffit de prendre la solution (1,1,.....1) pour le cas d'un système 3SAT sans clause négative.

On peut considérer que toute variable apparait  avec son opposé , en effet si une variable apparait seul alors on peut lui donner la valeur 1 et supprimer les clauses qui les contiennent.

 

 2-1)3SAT vers 1In3SAT :

 

On considère au départ un système 3SAT (1).

On procède de la manière habituelle, pour chaque clause (x,y,z) on associé trois clauses ( !x ,a,b ) (y,b,c) et (!z,b,d).

Ainsi à partir d'un système 3SAT avec  n variables et p clauses on construit un système 1In3SAT   contenant n+ 4p variables et 3p clauses.

Ce système 1In3SAT sera noté (2) dans la suite.

 

                                                             (1) est valide ssi (2) est valide.

 

 

2-2) De 1In3SAT vers 2In3SAT :

 

On introduit une nouvelle forme du système SAT : 2In3SAT ( exactement deux 1 sur 3 pour chaque clause).

En inversant les variables dans un système 1In3SAT on obtient un système 2In3SAT qui est d'une manière évidente NP-Complet;

On notera ce système (3) dans la suite .

 

                                                          (1)  Est valide ssi (3) est valide.

 

2-3) De 2n3SAT vers QPSD:

 

A chaque clause i  ( x,y,z) du système 2In3SAT (3)   on associe les deux équations suivantes dans le corps fini Z/2Z.

 

                                                         x*x + y*y + z*z =0
                                                                  et
                                                         x*Pi(x,y,z,x1…..xr) +y*Qi(x,y,z, x1…..xr) +z*Ri(x,y,z, x1…..xr) =1

 

ou Pi , Qi et Ri sont des polynômes quelconques  non nuls et x1…..xr sont des nouvelles variables .

 

La deuxième équation est un pivot qui permet d’éliminer la solution « parasite » (x,y,z) =(0,0,0).
Pour une variable négative !x on utilise évidemment 1+x dans le système dans Z/2Z.

On prend pour la suite des polynômes Pi, Qi et Ri de degré 1 seulement .

Chacun des polynômes choisis sera de la forme P= a1x1+ a2x2....................+ arxr. avec a1,......ar dans F2=Z/2Z.

Pour limiter la liberté  des nouvelles variables on ajoute aussi une équation qui  mélange ces variables , une somme des produits de xi par xj ou i!=j.

 

On construit ainsi un problème QP sur Z/2Z qu’on notera (4).

On a la conclusion:

                                                              (1)  est valide ssi  (4) admet une solution dans Z/2Z.

 

La liberté qu’on a de choisir autant de variables qu’on veut dans les polynômes P1,P2….Pm , Q1,Q2…Qm et R1,R2…Rm ( m est le nombre des clauses de (3))  permet de construire un système (4) qui est sous-déterminé.

 

Le problème (4) sera ainsi un problème QPSD.

 

3) Complexité:

 

Les transformations décrites dans les paragraphes 2-1 , 2-2 et 2-3 sont toutes polynomiales.

On sait qu’un système QPSD a une solution polynomial.

On a donc un algorithme polynomial pour résoudre un problème 3SAT.

 

4) Conclusion :

        P=NP

 
Remarques :

1) Une implémentation en c# de cette approche est en cours et sera disponible sous peu.

2) L'article qui expose la méthode de résolution polynomiale d'un QPSD est donnée dans l'article suivant. Quadratic system (424 Ko)