Chapitre 2 • Notions de complexité
50
NB : le lecteur se convaincra facilement que P ( NP.
S. Cook a conjecturé que cette inclusion est stricte : P 2 NP.
En dépit de nombreux effort, cette conjecture – à ce jour – n’a pas pu être démontrée : elle fait partie des “7 problèmes du millénaire” proposés en 2000 par le Clay
Mathematics Institute, chacun doté d’un million de dollars...
2.2.2 Les problèmes NP-complets
Au début des années 70, S. Cook a montré que parmi les problèmes de décision de la
classe NP, certains étaient plus difficiles à résoudre que d’autres. Il est conjecturé que
seuls des algorithmes énumératifs, de complexité de l’ordre de O1 2
n
2 , permettent la
résolution de ces problèmes appelés NP-complets. Le lecteur pourra consulter les
ouvrages que nous citons en bibliographie pour s’informer des preuves mathématiques
de NP-complétude. Avant de donner quelques exemples de problèmes NP-complets,
nous allons, de manière informelle, décrire les conséquences pratiques de ces résultats théoriques dans le quotidien du chercheur opérationnel. Contrairement à un problème polynomial, il est généralement vain d’essayer de résoudre optimalement des
problèmes NP-complets de grande taille. Seuls des problèmes de taille souvent très
inférieure aux tailles rencontrées dans le monde de l’entreprise peuvent être résolus
en temps raisonnable. En étant moins exigeant sur les contraintes des problèmes
ou sur la qualité des solutions demandées, le chercheur opérationnel, comme nous
le verrons plus loin, pourra toutefois envisager d’obtenir une solution acceptable
(approchée) au problème qui lui est posé.
Nous allons maintenant donner quelques exemples de problèmes NP-complets. Le
premier problème à avoir été montré NP-complet, est le problème de satisfiabilité,
défini de la manière suivante. Les données sont d’une part un ensemble de n variables
bimaires x 1 , c , x n , et, d’autre part, un ensemble de m « clauses » : une clause est un
sous-ensemble des 2n littéraux x 1 , c , x n , x 1 , c , x n , où x i désigne la variable complémentaire de x i ; ainsi 5x 1 , x 4 , x 10 6 est une clause. La question posée est : « Existe-t-il une
affectation de la valeur vrai ou faux à chacune des variables x i de sorte que pour chacune des m clauses, au moins l’un des littéraux la constituant ait la valeur vrai ? » Par
exemple, pour l’instance (jeu de données) construite sur l’ensemble des trois variables
x 1 , x 2 , x 3 et constituée des deux clauses 5x 1 , x 2 , x 3 6 et 5x 1 , x 3 6 en affectant les valeurs
vrai à x 2 et faux à x 1 et x 3 , les deux clauses sont satisfaites.
Remarque. En algèbre de Boole, on peut voir ces clauses comme des sommes
de variables booléennes affirmées ou niées : x 1 ~ x 2 ~ x 3 et x 1 ~ x 3 . La question
revient alors à déterminer si l’expression booléenne (x 1 ~ x 2 ~ x 3 ) ` (x 1 ~ x 3 )
peut être rendue égale à 1 en affectant à chaque variable une valeur égale à
0 ou 1.
Les problèmes du plus long chemin élémentaire (au sens du nombre d’arcs) et du
cycle hamiltonien dans un graphe quelconque (non valué), que nous avons définis
plus haut, ont eux aussi été montrés comme étant NP-complets ; par contre, le problème du plus long chemin élémentaire dans un graphe sans circuit est polynomial,
en O(m) pour un graphe de m arcs. De nombreux autres problèmes rencontrés tout
50
NB : le lecteur se convaincra facilement que P ( NP.
S. Cook a conjecturé que cette inclusion est stricte : P 2 NP.
En dépit de nombreux effort, cette conjecture – à ce jour – n’a pas pu être démontrée : elle fait partie des “7 problèmes du millénaire” proposés en 2000 par le Clay
Mathematics Institute, chacun doté d’un million de dollars...
2.2.2 Les problèmes NP-complets
Au début des années 70, S. Cook a montré que parmi les problèmes de décision de la
classe NP, certains étaient plus difficiles à résoudre que d’autres. Il est conjecturé que
seuls des algorithmes énumératifs, de complexité de l’ordre de O1 2
n
2 , permettent la
résolution de ces problèmes appelés NP-complets. Le lecteur pourra consulter les
ouvrages que nous citons en bibliographie pour s’informer des preuves mathématiques
de NP-complétude. Avant de donner quelques exemples de problèmes NP-complets,
nous allons, de manière informelle, décrire les conséquences pratiques de ces résultats théoriques dans le quotidien du chercheur opérationnel. Contrairement à un problème polynomial, il est généralement vain d’essayer de résoudre optimalement des
problèmes NP-complets de grande taille. Seuls des problèmes de taille souvent très
inférieure aux tailles rencontrées dans le monde de l’entreprise peuvent être résolus
en temps raisonnable. En étant moins exigeant sur les contraintes des problèmes
ou sur la qualité des solutions demandées, le chercheur opérationnel, comme nous
le verrons plus loin, pourra toutefois envisager d’obtenir une solution acceptable
(approchée) au problème qui lui est posé.
Nous allons maintenant donner quelques exemples de problèmes NP-complets. Le
premier problème à avoir été montré NP-complet, est le problème de satisfiabilité,
défini de la manière suivante. Les données sont d’une part un ensemble de n variables
bimaires x 1 , c , x n , et, d’autre part, un ensemble de m « clauses » : une clause est un
sous-ensemble des 2n littéraux x 1 , c , x n , x 1 , c , x n , où x i désigne la variable complémentaire de x i ; ainsi 5x 1 , x 4 , x 10 6 est une clause. La question posée est : « Existe-t-il une
affectation de la valeur vrai ou faux à chacune des variables x i de sorte que pour chacune des m clauses, au moins l’un des littéraux la constituant ait la valeur vrai ? » Par
exemple, pour l’instance (jeu de données) construite sur l’ensemble des trois variables
x 1 , x 2 , x 3 et constituée des deux clauses 5x 1 , x 2 , x 3 6 et 5x 1 , x 3 6 en affectant les valeurs
vrai à x 2 et faux à x 1 et x 3 , les deux clauses sont satisfaites.
Remarque. En algèbre de Boole, on peut voir ces clauses comme des sommes
de variables booléennes affirmées ou niées : x 1 ~ x 2 ~ x 3 et x 1 ~ x 3 . La question
revient alors à déterminer si l’expression booléenne (x 1 ~ x 2 ~ x 3 ) ` (x 1 ~ x 3 )
peut être rendue égale à 1 en affectant à chaque variable une valeur égale à
0 ou 1.
Les problèmes du plus long chemin élémentaire (au sens du nombre d’arcs) et du
cycle hamiltonien dans un graphe quelconque (non valué), que nous avons définis
plus haut, ont eux aussi été montrés comme étant NP-complets ; par contre, le problème du plus long chemin élémentaire dans un graphe sans circuit est polynomial,
en O(m) pour un graphe de m arcs. De nombreux autres problèmes rencontrés tout