Pourquoi ne pas ajouter d'autres variables pour résoudre le problème 3SAT

[extrazlove]

Bonjour à toutes et à tous,

Pourquoi ne pas ajouter d'autres variables pour obtenir une matrice inversible, afin de résoudre le problème 3SAT en temps polynomial ?


En clair, on peut transformer le problème 3SAT en avec un vecteur et 1 le vecteur des 1, mais le déterminant est souvent nul, donc $A^{-1}$ n'existe pas. Cependant, en supposant que, puisque j'ai la forme du déterminant, je pourrais construire un algorithme en temps polynomial où j'ajoute d'autres variables pour ne plus avoir un déterminant nul, je pourrais alors trouver et la résolution serait en temps polynomial pour trouver ou il y a .

Voici un exemple :

et et donc le matrice inversible est ici j'ai donc
Donc tout les calcules son en modulo 2
J'ai bien vérfier et et


Donc si j'ai des Cn avec plusieurs variables il suffit de trouver [/TEX]A[/TEX] inversible ou même si il n'est pas inversible il suffit d'ajouter des variables et des équations de plus pour le rendre inversible est avoir un nouveau matrice inversible comme ça il suffit de calculer pour trouver ou tout et ou est dans et est dans et tous ça en temps plynomniale...
-----

[MissJenny]

si tu considère le système linéaire Ax=B où A est une matrice non inversible, il se peut que B ne soit pas dans l'image de A, et dont le système n'a pas de solution. Si tu "ajoutes des variables" (tu devrais montrer comment tu fais en pratique) tu vas peut-être bien obtenir un système qui a des solutions, mais les solutions vont dépendre des valeurs ajoutées et tu ne pourras pas en déduire une solution de ton système initial (puisqu'il n'en a pas).