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).

[extrazlove]

Voici ce que je veux faire:

Pour une matrice inversible « A », les solutions de l'équation « A x = 1 (mod 2) » et celles obtenues en satisfaisant une condition logique OU peuvent parfois coïncider, mais ce n'est pas toujours le cas. Les différences proviennent de la nature des opérations impliquées :

1. Propriétés d'une matrice inversible mod 2

a) Si « A » est inversible modulo 2, cela signifie que « A » est une matrice carrée et que chaque colonne de « A » est linéairement indépendante.

b)Ainsi, l'équation « A x = 1 (mod 2) » a une solution unique pour « x » sur le corps fini à deux éléments (0 et 1). Cependant, la condition OU ne garantit pas une solution unique ; elle nécessite seulement de trouver des combinaisons de « x » qui satisfont au moins un « 1 » dans chaque ligne. Cela signifie qu'il pourrait y avoir plusieurs vecteurs « x » qui satisfont à la condition OU, même si « A » est inversible.

2. Cas où les solutions coïncident

a) Les solutions de « A x = 1 (mod 2) » et la condition OU coïncideront si et seulement si la solution unique à l'équation linéaire satisfait également la condition de couverture requise par l'OR.

b) Cela se produit dans les cas où chaque ligne de « A » contient un « 1 » dans les positions correspondant à la solution unique de « A x = 1 (mod 2) ». En d'autres termes, si la solution « x » de « A x = 1 (mod 2) » « active » chaque ligne de « A », alors cette solution satisfera également la condition OU.

c)Cependant, même dans ce cas, la condition OU ne garantit pas qu’il s’agisse de la seule solution possible, car le OU logique peut permettre des solutions supplémentaires.

3. Cas où les solutions diffèrent

Si chaque ligne de « A » n’est pas activée uniquement par la solution de « A x = 1 (mod 2) », alors il est possible que la condition OU admette des solutions supplémentaires qui ne satisfont pas l’équation linéaire.

Cela se produit particulièrement si d'autres combinaisons de 0 et de 1 dans « x » couvrent les « 1 » requis dans chaque ligne sans satisfaire strictement « A x = 1 (mod 2) ».

Par conséquent, pour une matrice inversible « A », l'équation linéaire a une solution unique, tandis que la condition OU peut admettre plusieurs solutions, y compris potentiellement la solution de « A x = 1 (mod2) » mais sans s'y limiter.

Conclusion Pour une matrice inversible « A », les solutions de « A x = 1 (mod 2) » et celles satisfaisant la condition OU ne coïncideront que si la solution unique de l'équation linéaire satisfait également la condition OU pour chaque ligne. Cependant, en général, la condition OU peut avoir plus de solutions, incluant potentiellement d'autres vecteurs « x » au-delà de la solution unique de l'équation linéaire.

Question :

Pouvons-nous ajouter d'autres variables pour satisfaire la condition 2.b et résoudre le problème 3-SAT en temps polynomial en le résolvant en MOD 2, étant donné que les deux solutions coïncident ?

Plus clairement, on transforme le problème 3-SAT en un problème consistant à trouver une matrice inversible mod 2 qui respecte certaines conditions en ajoutant des variables supplémentaires.

Pour trouver ce matrice il suffit de calculer delat a chaque ajout, mais je peux réduire le calcule de delta car je vais modifier que quelque variable pour obtenir 1.