NP-COMPLETUDE

INTRODUCTION

Dans le but d’analyser et de comparer des algorithmes, on utilise souvent l’approche dite du “pire cas”. Cette approche consiste en gros à évaluer comment le temps d’exécution d’un algorithme est relié à la taille de la donnée d’entrée (input). Dans ce type de calcul, on ignore généralement certains facteurs constants qui ne peuvent être contrôlés par le programmeur tels que la traduction en langage machine du programme dans lequel l’algorithme est écrit, le type d’ordinateur sur lequel le programme va rouler, etc... De plus on s’intéresse davantage à évaluer la performance de l’algorithme pour les grandes tailles d’entrée que pour les petites. Tous les algorithmes étudiés jusqu’ici étaient des algorithmes à temps polynomial : sur des entrées de taille n, leur temps d’exécution dans le pire des cas est O(n^k) pour une certaine constante k. Il est naturel de se demander si tous les problèmes peuvent être résolus en temps polynomial. La réponse est non. Par exemple, il existe des problèmes, tel le fameux « problème de l’arrêt de Turing d’une machine », qui ne peuvent être résolus par aucun ordinateur, quel que soit le temps qu’il y passe. Il existe aussi des problèmes qui peuvent être résolus, mais pas en temps O(n^k) pour une constante k quelconque. De manière générale, on considère que les problèmes résolubles par des algorithmes à temps polynomial sont traitables (faciles) et que les problèmes nécessitant un temps supra-polynomial (dits NP-Complets) sont intraitables (difficiles). Dans ce qui suit, on présentera tout d’abord les classes P et NP, on montrera la NP-complétude, ensuite on présentera la machine de Turing et enfin quelques problèmes et montrer qu’ils sont  NP-complet.

HISTORIQUE

Le concept de NP-complétude a été introduit en 1971 par Stephen Cook dans une communication intitulée The complexity of theorem-proving procedures (La complexité des procédures de démonstration de problèmes), bien que le mot « NP-complet » n'apparaisse pas explicitement dans l'article. Lors de la conférence à laquelle il a été présenté, une discussion acharnée a eu lieu entre les chercheurs présents pour savoir si les problèmes NP-complets pouvaient être résolus en temps polynomial sur machine de Turing déterministe. John Hopcroft a finalement convaincu les participants que la question devait être remise à plus tard, personne n'ayant réussi à démontrer ou infirmer le résultat.

La question de savoir si P = NP n'est toujours pas résolue. Elle fait partie des problèmes du prix du millénaire, un ensemble de sept problèmes pour lesquels l'Institut de mathématiques Clay offre un prix d'un million de dollars. Il « suffirait » de trouver un seul problème NP qui soit à la fois NP-complet et P pour démontrer cette hypothèse, ou d'exhiber un seul problème NP qui ne soit pas dans P pour démontrer sa négation.

Le résultat de l'article de Cook, démontré de manière indépendante par Leonid Levin en URSS, est maintenant connu sous le nom de théorème de Cook-Levin. Ce théorème affirme qu'il existe un problème NP-complet. Cook a choisi le problème SAT et Levin un problème de pavage. En 1972, Richard Karp a prouvé la NP-complétude de plusieurs autres problèmes fondamentaux en informatique et très disparates, connus comme la liste des 21 problèmes NP-complets de Karp. Depuis, on a démontré la NP-complétude des  milliers d'autres problèmes.

1. PRESENTATION DES CLASSES

Un problème de décision est un problème dont la réponse est OUI ou NON/ VRAI ou FAUX (il pleut ? 3 est un nombre pair ?). Pour un problème P, notons O(P) l’ensemble des instances de P dont la réponse est OUI. Ainsi selon la difficulté à résoudre efficacement un problème et à vérifier la véracité de sa solution, on distingue :

1. La classe P

La classe de complexité P ou classe Polynomiale se compose des problèmes qui sont résolubles en temps polynomial par rapport à la taille de l’entrée. Autrement dit cette classe regroupe les problèmes qui sont résolubles en temps O(n^k) pour une certaine constance k ( n est la taille des entrées) . C’est la classe des problèmes dits faciles. On dit aussi, pour abréger, que l'algorithme lui-même est polynomial. Les algorithmes efficaces sont polynomiaux, c’est à dire les algorithmes non polynomiaux sont certainement inefficaces. A titre d’exemple, nous pouvons citer : le problème du plus court chemin (Dijkstra) et le problème de la détermination de l’arbre de recouvrement de poids minimum (Prim et Kruskal).

2. La classe NP

La classe NP se compose des problèmes qui sont « vérifiables » en temps polynomial. Cela signifie : si l’on nous donne, d’une façon ou d’une autre, une solution « certifiée », nous pouvons vérifier que cette solution est correcte en temps polynomial par rapport à la taille de l’entrée. Par exemple, dans le problème du circuit hamiltonien, étant donné un graphe orienté G =(S, A), une solution certifiée serait une suite (v₁, v₂, v₃,..., v|_S|) de|S| sommets. Il est facile de vérifier en temps polynomial que (v_i, v_i+1) ∈ A pour i =1, 2,3,..., |S|−1 et que (v_|S|, v1) ∈ A aussi.

Théorème : P ⊆ NP

Preuve : Soit p ∈ P et soit A un algorithme polynomial permettant de résoudre chaque instance de P. Pour une instance  p ϵ O(P) , on peut vérifier que  p ϵ O(P)  en appliquant A, qui donne la réponse OUI en un temps0 polynomial.  Ceci prouve que P ⊆ NP .

3. La classe NP-Complet

La classe NP-complet contient les problèmes les plus difficiles de NP. Ces problèmes semblent vraiment ne pas faire partie de P (bien que à l’heure actuelle on ne possède pas une réponse définitive, voir la question irrésolue P = NP ?). Si nous sommes capables de trouver un moyen de résoudre efficacement (algorithme polynomial) un problème de NP-complet, nous pouvons alors utiliser cet algorithme pour résoudre tous les problèmes de NP.

En effet, un problème X appartient à NP-complet s’il est dans NP et si tout autre problème dans NP peut s’y réduire. On n’en déduit qu’une méthode “assez facile” pour prouver qu’un nouveau problème appartient à NP-complet est de montrer d’abord qu’il est dans NP, ensuite le réduire en un problème connu dans NP-complet. Par conséquent il est très utile de connaître une variété de problèmes NP-complets.

1. NP-COMPLETUDE

La raison qui pousse le plus les théoriciens de l’informatique à croire que P ≠ NP est sans doute l’existence de la classe des problèmes «NP-complets ». Cette classe possède une propriété surprenante : si un problème NP-complet peut être résolu en temps polynomial, alors tous les problèmes de NP peuvent être résolus en temps polynomial, autrement dit, P = NP. Pourtant, malgré des années de recherches, aucun algorithme polynomial n’a jamais été découvert pour quelque problème NP-complet que ce soit.

Les langages NP-complets sont, dans un sens, les langages les plus « difficiles » de NP. La réductibilité en temps polynomial va donc nous permettre de comparer des problèmes.

1. Réduction polynomiale

Cette notion permettant de montrer qu’un problème n’est pas plus difficile ou plus facile qu’un autre, s’applique même quand les deux problèmes sont des problèmes de décision. Nous exploiterons cette idée dans la quasi-totalité des démonstrations de NP-complétude, et ce de la façon suivante. Soit un problème de décision, disons A, que l’on voudrait résoudre en temps polynomial. L’entrée d’un problème particulier est dite instance de ce problème ;
Supposons maintenant qu’il y ait un autre problème de décision, disons B, que nous savons déjà comment résoudre en temps polynomial. Enfin, supposons que nous ayons une procédure qui transforme toute instance a de A en une certaine instance b de B et qui a les caractéristiques suivantes :

• La transformation prend un temps polynomial.
• Les réponses sont les mêmes. C’est à dire, la réponse pour a est « oui » si et seulement si la réponse pour b est « oui ».

Une telle procédure porte le nom de réduction à temps polynomial et, comme le montre la figure si dessous, elle donne un moyen de résoudre le problème A en temps polynomial : Étant donnée une

• Instance a de A, utiliser une réduction à temps polynomial pour la transformer en une instance b de B.
• Exécuter l’algorithme de décision à temps polynomial de B sur l’instance b.
• Utiliser la réponse pour b comme réponse pour a.
•  
  Si chacune de ces étapes prend un temps polynomial, il en est de même de l’ensemble ; on a donc un moyen de décider pour a en temps polynomial. Autrement dit, en « réduisant » la résolution du problème A à celle du problème B, on se sert de la « facilité » de B pour prouver la « facilité » de A.

En nous rappelant que la NP-complétude consiste à démontrer le niveau de difficulté d’un problème et non son niveau de facilité, nous pouvons utiliser des réductions à temps polynomial, en sens inverse, Pour prouver qu’un problème est NP-complet. Poussons l’idée un cran plus loin et montrons comment nous pourrions employer des réductions à temps polynomial pour prouver qu’il ne peut exister d’algorithme à temps polynomial pour un certain problème B. Supposons que l’on ait un problème de décision A pour lequel on sait déjà qu’il ne peut pas exister d’algorithme à temps polynomial. (Nous laisserons de côté, pour l’instant, le problème de savoir comment trouver un tel problème A.) Supposons, en outre, que l’on ait une réduction à temps polynomial qui transforme des instances de A en instances de B. On peut alors utiliser un raisonnement simple par l’absurde pour prouver qu’il ne peut pas exister d’algorithme à temps polynomial pour B. Supposons le contraire, c’est à dire que B ait un algorithme à temps polynomial. Alors, en utilisant la méthode illustrée à la figure1, on aurait un moyen de résoudre A en temps polynomial, ce qui est contraire à l’hypothèse selon laquelle il n’y a pas d’algorithme à temps polynomial pour A. Pour la NP-complétude, on ne peut pas partir du principe qu’il n’y a absolument pas d’algorithme à temps polynomial pour le problème A. Cependant, la méthodologie de la démonstration est la même : nous prouvons que le problème B est NP-complet en supposant que le problème A est lui aussi NP-complet.