Introduction à la NP-complétude
Marc Parizeau
Département de génie électrique et de génie informatique
Université Laval
Hiver 98
Dans ce document, nous allons introduire le concept de NP-complétude c’est-à-dire que
nous allons tenter de définir sans trop de formalismes la classe des problèmes dit NP-complets.
Ces problèmes sont ceux pour lesquels personne à l’heure actuelle ne connait d’algorithme ef-
ficace (i.e. seulement des algorithmes de complexité exponentielle). Ce sont donc des problèmes
vraiment difficiles par opposition à ceux pour lesquels on connait des algorithmes de com-
plexité polynomiale.
Mais avant de définir cette classe de problèmes vraiment difficiles, définissons d’abord
les classes P et NP.
1 Classe P
La classe P contient tous les problèmes relativement faciles c’est-à-dire ceux pour lesquels
on connait des algorithmes efficaces. Plus formellement, ce sont les problèmes pour lesquels
on peut construire une machine déterministe (e.g. une machine de Turing1) dont le temps
d’exécution est de complexité polynômiale (le sigle P signifie “Polynomial time”).
Tous les algorithmes dont nous avons discuté jusqu’à présent appartiennent à cette classe.
2 classe NP
Les problèmes de la classe NP sont ceux pour lesquels on peut construire une machine de Tu-
ring non déterministe dont le temps d’exécution est de complexité polynômiale. Notez bien
1
Je vous réfère ici aux notes du cours IFT-19496 Mathématiques discrètes du GIF pour la définition de ce
qu’est une machine de Turing.
1
2 3 CLASSE NP-COMPLET
que le sigle NP provient de “Nondeterministic Polynomial time” (et non de “Non Polyno-
mial”).
Contrairement aux machines déterministes qui exécutent une séquence d’instructions bien
déterminée, les machines non déterministes ont la remarquable capacité de toujours choisir
la meilleure séquence d’instructions qui mène à la bonne réponse lorsque celle-ci existe. Il va
sans dire qu’une telle machine ne peut pas exister autrement que dans l’esprit d’un théoricien!
Néanmoins, comme nous le verrons par la suite, ce concept abstrait n’est pas sans intérêt et
constitue en fait la base de toute la théorie de la NP-complétude.
Il importe de remarquer à ce stade de la discussion que la classe P est incluse dans la classe
NP, on écrit P NP, car si l’on peut construire une machine déterministe pour résoudre ef-
ficacement un problème, on peut certainement (au moins dans notre esprit) en construire une
non déterministe qui résout aussi efficacement le même problème. Par ailleurs, il ne faut pas
croire que ce concept de divination optimale qu’est la machine non déterministe permet de
tout résoudre puisqu’il existe en informatique théorique d’autres types de problèmes n’appar-
tenant pas à la classe NP (e.g. les problèmes indécidables).
Pour savoir si un problème donné appartient ou non à la classe NP il s’agit simplement de
l’exprimer sous la forme d’une question dont la réponse est soit oui, soit non. Le problème
appartient alors à la classe NP si on arrive à démontrer à l’aide d’un algorithme de complexité
polynômiale que n’importe quelle instance oui du problème est belle et bien correcte. On n’a
pas à se préoccuper des instances non du problème puisque la machine non déterministe, par
définition, prend toujours la bonne décision (lorsque celle-ci existe). Par exemple, le problème
consistant à trouver un cycle hamiltonien2 dans un graphe appartient à NP puisque, étant
donné un cycle, il est trivial de vérifier en temps linéaire qu’il contient bien une et une seule
fois chaque sommet.
3 Classe NP-complet
Parmi l’ensemble des problèmes appartenant à NP, il en existe un sous-ensemble qui contient
les problèmes les plus difficiles : on les appelle les problèmes NP-complet. Un problème NP-
complet possède la propriété que tout problème dans NP peut être transformé en celui-ci en
temps polynômial.
Pour transformer un problème P1 en un problème P2 , on dit souvent réduire P1 en P2 ,
et on écrit P1 / P2 , il s’agit simplement de définir une application f qui met en relation les
instances de P 1 avec celles de P 2 :
f : P1 ! P2
2
Un cycle qui passe une et une seule fois par tous les sommets du graphe.
3
Il reste alors à montrer que l’on peut construire une telle application en temps polynômial. Par
exemple, dans un calculateur de poche, on entre habituellement les nombres en base 10 mais
les algorithmes de calcul fonctionnent en base 2. Il faut donc transformer le problème, c’est-
à-dire le réduire, en convertissant les nombres de la base 10 vers la base 2, puis appliquer les
algorithmes de calcul et, finalement, reconvertir le résultat vers la base 10.
La raison essentielle pour laquelle les problèmes NP-complets sont les plus difficiles
parmi les problèmes de NP est que ces premiers peuvent toujours servir comme des sous-
routines pour solutionner ces derniers à condition de rajouter l’étape de réduction, étape tou-
jours facile puisque réalisable en temps polynômial! Un problème NP-complet est donc
complet en ce sens qu’il contient l’essentiel de la complexité des problèmes appartenant à
NP, et qu’une solution polynômiale à ce problème implique une solution polynômiale à tous
les problèmes de NP.
Supposons maintenant que nous savons qu’un certain problème P1 est NP-complet et que
P2 appartient à NP. Supposons par ailleurs que l’on arrive à démontrer que P1 / P2 (en
temps polynômial), alors cela implique que P2 appartient aussi à NP-complet puisque par
définition :
8P 2 NP; P / P1
et donc par fermeture sur la réduction :
8P 2 NP; P / P2
4 Exemple
Considérons maintenant l’exemple du problème du commis voyageur :
Soit G = (S; A; ) un graphe complet valué et K une constante positive. Le
problème du commis voyageur consiste à déterminer s’il existe un cycle hamil-
tonien (i.e. qui passe une et une seule fois par tous les sommets de G) dont le
poids est K ?
Notez bien que ce problème qui semble a priori théorique et sans grand intérêt possède en fait
plusieurs applications importantes. Par exemple, la fabrication de nombreux produits requiert
de pouvoir perforer une surface plane en plusieurs endroits (on peut penser en autres aux
circuits imprimés). Ces perforations sont habituellement réalisées par un dispositif mécanique
(e.g. un robot) qui se déplace d’un trou à l’autre. Pour optimiser le procédé de fabrication, il
importe autant que possible de minimiser le déplacement total du dispositif de perforation.
Les sommets S du graphe G représenteraient donc les trous alors que les poids des arêtes
représenteraient le temps requis pour passer d’un trou à l’autre. Le problème consiste donc à
trouver un chemin fermé (cycle) qui nécessite moins qu’un certain temps K pour percer tous
4 5 CONCLUSION
les trous et revenir au point de départ (K pourrait correspondre au temps qui rend le procédé
économiquement rentable).
Pour prouver que ce problème est NP-complet, il faut partir d’un autre problème que l’on
sait NP-complet et tenter de le réduire. Pour se faire, nous allons donc supposer que l’on
a déjà démontré que le problème qui consiste à déterminer s’il existe dans un graphe (pas
nécessairement complet ni valué) un cycle hamiltonien est NP-complet.
Premièrement, on voit facilement que le problème du commis voyageur appartient à la
classe NP puisqu’on peut vérifier en temps linéaire qu’une solution donnée (par une machine
non déterministe) est un cycle hamiltonien de poids K . Pour montrer qu’il est NP-complet,
il reste à trouver une application qui réduit n’importe quelle instance du problème de cycle
hamiltonien en une instance de commis voyageur.
Soit le graphe G = (S; A) d’une instance quelconque du problème de cycle hamiltonien.
Construisons le graphe complet et valué G = (S; A ; ) possédant le même ensemble de
0 0
sommets. À chaque arête a 2 A associons les poids suivants :
0
(
(a) = 1 si a2A
2 si a 62 A
et choisissons K = jS j. On constate aisément que G possède un cycle hamiltonien si et seule-
ment si G posséde un cycle de commis voyageur avec un poids K = jS j, ce qui démontre ef-
0
fectivement la réduction recherchée. Or celle-ci peut s’effectuer en temps polynômial puisque
le nombre d’arêtes dans G est O (n2 ) si n représente le nombre de sommets. Par conséquent,
0
le problème du commis voyageur est bien NP-complet si celui du cycle hamiltonien l’est
aussi. . .
5 Conclusion
Il existe aujourd’hui un long répertoire de problèmes NP-complet [1]. Parmi ceux-ci, on
retrouve de nombreux problèmes relatifs aux systèmes d’exploitation, aux systèmes de base
de données, à la recherche opérationnelle, à la logique et à la théorie des graphes (dont les
problèmes de coloriage et de clique). Tous ces problèmes ont été démontré comme faisant
partie de la classe NP-complet en employant la même technique que celle que nous avons
utilisé pour le problème du commis voyageur, bien que la transformation à faire pour réduire
le problème ne soit pas toujours aussi directe que celle de notre exemple et que, souvent, il
ne soit même pas facile de choisir adéquatement le bon problème NP-complet de départ.
Par ailleurs, une question importante demeure en suspend : comment a-t’on bien pu
démontrer le premier problème NP-complet? ! Eh bien c’est un dénommé Cook en 1971 qui
a réussi ce tour de force en utilisant directement la définition du concept de NP-complétude
à savoir en montrant à l’aide d’une certaine machine de Turing non déterministe que tous
RÉFÉRENCES 5
les problèmes de NP peuvent être réduits en temps polynômial en un problème dit de “sa-
tisfaisabilité”. Ce problème consiste à vérifier s’il existe au moins un ensemble de valeurs
pour les variables d’une expression booléenne quelconque qui “satisfont” cette expression,
c’est-à-dire qui font en sorte que l’expression soit vrai. Et c’est de cette démonstration (par
ailleurs fort complexe) que découle toutes les autres.
Finalement, ce qu’il importe de bien comprendre et de retenir de toute cette théorie, son
idée maı̂tresse, est que si l’on trouve un jour un algorithme de complexité polynômiale pour
un seul de ces problèmes vraiment difficiles que sont les problèmes NP-complet, alors d’un
seul coup NP devient égal à P et tous les problèmes difficiles deviennent faciles!
Références
[1] Michael R. Garey, David S. Johnson, Computers and Intractability — A Guide to the
Theory of NP-Completeness, W.H. Freeman and Company, 1979.
