Salut,
On peut réécrire sat (pb NP-complet) comme un problème d'optimisation convexe :
se traduit par
de plus on ajoute :
,
,
,
et
pour tout
![]()
Le but étant de minimiser.
Si l'on trouve une solution avecc'est que le problème sat à une solution.
Ainsi, sat deviendrait soluble avec la méthode des ellipsoïdes par exemple.
Y-voyez vous une erreur ?
Merci.
-----