Complexité des problèmes et heuristiques
181
Par exemple, on peut transformer le problème de l'existence d'un circuit hamiltonien
dans un graphe orienté en un problème d'existence d'une solution dans un programme
linéaire en variables bivalentes (on pose
ou suivant que l'arc appartient
au circuit recherché et on exprime ensuite le fait que l'on a affaire à un circuit
hamiltonien)
Si
sont dits équivalents.
On peut proposer une relation un peu plus complexe pour les problèmes d'optimisation :
Soit un problème de ce type :
et le problème :
S'il existe une bijection de
sur
, calculable en un temps polynomial, et telle
que :
1
2
1
))
(
(
=
)
(
D
x
x
g
z
x
z
et
2
2
2
2
2
)
(
>
)
(
'
'
D
D
u
D
v
v
z
u
z
alors est dit fortement réductible à .
La première condition exprime que toute solution optimale de
se conserve dans la
bijection ; la seconde permet d'éliminer les solutions de
qui ne sont pas solution de
Deux problèmes
qui sont tels que
est fortement réductible à
et
fortement réductible à sont fortement équivalents.
Ces relations sont importantes à cause des résultats suivants :
e) Problèmes NP-complets et NP-difficiles
Un problème d'existence NP est dit NP-complet si tout problème de NP lui est
faiblement réductible. En d'autres termes, s'il existe des problèmes NP-complets, et si on
démontre qu'un quelconque de ces problèmes se résout de façon polynomiale, alors tous
les problèmes NP sont polynomiaux ! Une telle possibilité est confirmée par le théorème
de Cook (1970), qui a trouvé de tels problèmes NP-complets en travaillant sur la logique
des propositions : soit variables booleiennes
(prenant les valeurs
) et leurs
conjuguées
(
si
et
si
), et soit m sous-ensembles des
variables
et . Ces sous-ensembles sont appelés des clauses. Si une des clauses
comporte au moins une variable égale à 1, elle est dite satisfaite. Le problème suivant :