Problème NP-complet

Problème NP-complet

En théorie de la complexité, un problème NP-complet est un problème de décision vérifiant les propriétés suivantes :

  • Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP.
  • Tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP.

Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP-complet, on ne sait pas en trouver efficacement. Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps d'exécution exponentiel en la taille de l'entrée dans le pire cas, et sont donc inexploitables en pratique même pour des instances de taille modérée.

La seconde propriété de la définition implique que s'il existe un algorithme polynomial pour n'importe quel problème NP-complet, alors tous les problèmes de la classe NP peuvent être résolus en temps polynomial. Trouver un algorithme polynomial pour un problème NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P ≠ NP, une question ouverte qui fait partie des problèmes non résolus en mathématiques les plus importants à ce jour.

En pratique, les informaticiens et les développeurs sont souvent confrontés à des problèmes NP-complets. Dans ce cas, savoir que le problème sur lequel on travaille est NP-complet est une indication du fait que le problème est difficile à résoudre, donc qu'il vaut mieux chercher des solutions approchées en utilisant des algorithmes d'approximation.

Sommaire

Définition formelle

Les classes P et NPC sont incluses dans NP, et disjointes si P \not= NP. On ne sait pas si NP - (NPC \cup P) (représenté ici par la section médiane de l'ovoïde NP), est vide.

Un problème de décision peut être décrit mathématiquement par un langage formel, dont les mots correspondent aux instances du problème pour lesquelles la réponse est oui. Sans perte de généralité, on peut supposer que tous les langages qu'on considère sont définis sur le même alphabet Σ.

Deux classes de complexité, présentées de manière plus détaillée dans Théorie de la complexité, interviennent dans la définition de la NP-complétude :

Un langage L\, est NP-difficile s’il existe une réduction polynomiale de tout langage L' \in NP\, à L\,, c’est-à-dire une fonction f : \Sigma^* \mapsto \Sigma^*\, (où \Sigma\, est l’alphabet de ces langages), calculable en temps polynomial sur une machine de Turing déterministe, telle que :

\forall w \in \Sigma^*, w \in L' \Leftrightarrow f(w) \in L\,.

Si de plus L \in NP\,, alors le langage L\, est NP-complet.

La classe des langages NP-complets est notée NPC\,.

On dit qu’un problème de décision est « NP-complet » lorsque le langage correspondant est NP-complet. C’est une notion informelle car il existe plusieurs moyens de coder les instances d’un problème, mais cela ne pose pas de difficultés dans la mesure où on emploie un codage raisonnable du problème vers le langage considéré (voir la section NP-complétude faible).

Par abus de langage, on qualifie souvent de « NP-complets » des problèmes d'optimisation et non des problèmes de décision. Ainsi, on dira que le problème du voyageur de commerce, qui consiste à trouver un plus court circuit passant une seule fois par chacun des sommets d'un graphe connexe fini, est NP-complet. Cela se justifie par le fait qu'on peut transformer tout problème d’optimisation en problème de décision et réciproquement (voir la section « De l’existence à la décision » de l’article sur la théorie de la complexité).

Histoire

Le concept de NP-complétude a été introduit en 1971 par Stephen Cook dans un article intitulé The complexity of theorem-proving procedures[1] (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 informaticiens 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 prouver cette hypothèse, ou de trouver un seul problème NP qui ne soit pas dans P pour prouver le contraire.

Le résultat de l'article de Cook, démontré de manière indépendante par Leonid Levin, est maintenant connu sous le nom de théorème de Cook-Levin. Ce théorème affirme que le problème SAT est NP-complet. En 1972, Richard Karp a prouvé la NP-complétude de plusieurs autres problèmes, les 21 problèmes NP-complets de Karp. Depuis, on a démontré la NP-complétude de milliers d'autres problèmes.

Preuves de NP-complétude

Pour démontrer la NP-complétude d'un nouveau problème Π1 ∈ NP, la méthode usuelle consiste à trouver un problème NP-complet Π2 déjà connu qui se réduit à Π1. Cela suffit à démontrer que Π1 est NP-complet. En effet, pour tout Π ∈ NP, on a Π ≤P Π2P Π1 (la relation de réduction polynomiale ≤P est transitive).

Pour illustrer cette méthode, voici une démonstration de la NP-complétude de l'optimisation linéaire en nombres entiers (OLNE) par une réduction à partir de SAT, qui est NP-complet comme expliqué plus haut.

L'OLNE consiste à déterminer si un système d'inéquations linéaires a au moins une solution entière.

Exemple
2y ≥ 1, 2y - 4x ≤ 1, 2y + 4x ≤ 6 a une solution entière (x = 1, y = 1) ;
2y ≥ 1, 2y - 4x ≤ 1, 2y + 4x ≤ 5 n'a aucune solution entière.

SAT consiste à déterminer si une formule logique sous forme normale conjonctive est satisfiable.

Exemple
(v_1 \lor v_2) \land (v_1 \lor \lnot v_2) \land (\lnot v_1 \lor \lnot v_2) est satisfiable en posant v1=vrai et v2=faux.
(v_1 \lor v_2) \land (v_1 \lor \lnot v_2) \land (\lnot v_1) n'est pas satisfiable.

Le problème de l'OLNE est bien un problème NP : vérifier qu'une assignation des variables est solution est réalisable efficacement[2]. On définit la fonction de réduction f de la façon suivante. Soit ϕ une formule sous forme normale conjonctive. On définit f(ϕ) comme étant le problème d'OLNE suivant :

  • À chaque variable vi correspond une variable xi du système. De plus, on ajoute au système la contrainte 0 ≤ xi ≤ 1.
  • Pour chaque clause de la forme v_1 \lor \dots \lor v_k \lor \lnot v_{k+1} \lor \dots \lor \lnot v_n, avec v_1,\dots,v_n des variables pas forcément distinctes, on ajoute au système la contrainte x_1+\dots+x_k+(1-x_{k+1})+\dots+(1-x_n) \geq 1.
Exemple
Pour la formule (v_1 \lor v_2) \land (v_1 \lor \lnot v_2) \land (\lnot v_1 \lor \lnot v_2), le système linéaire contient cinq inéquations :
0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x1 + x2 ≥ 1, x1 + (1 - x2) ≥ 1 et (1 - x1) + (1 - x2) ≥ 1.

On constate alors que si ϕ est satisfiable, alors en posant :

  • xi = 0 si vi=faux,
  • xi = 1 si vi=vrai,

on obtient une solution du problème d'OLNE. Réciproquement, si le problème d'OLNE a une solution, alors la formule peut être satisfaite en mettant à vrai les variables vi telles que xi = 1. Ainsi, la fonction f est bien une réduction de SAT à l'OLNE. De plus, f est calculable en temps polynomial donc l'OLNE est un problème NP-complet.

Liste de problèmes NP-complets

Chaîne des réductions communément utilisées pour prouver la NP-complétude de quelques problèmes classiques
Article détaillé : Liste de problèmes NP-complets.

Parmi les problèmes NP-complets notables, on peut citer :

Il est à noter qu'il s'agit alors d'un abus de langage de parler de problème NP pour certains de ces problèmes, car ils ne sont pas des problèmes de décision. Cependant, les problèmes de décision associés à un problème d'optimisation, typiquement de la forme : "telle solution est-elle optimale ?" ou "existe-t-il une solution de coût inférieur à... ?", sont eux bien NP-complets.

Le schéma de droite indique, pour une partie de ces problèmes, dans quel ordre on prouve en général la NP-complétude. On notera que cet ordre de réduction n'est pas le seul possible, puisque par définition, il existe toujours une réduction entre deux problèmes NP-complets quelconques. Son intérêt est de simplifier les démonstrations.

Contre-exemples

Parfois, une modification mineure transforme un problème NP-complet en problème de la classe P. Quelques exemples :

  • 3-SAT, restriction de SAT au cas où toutes les clauses ont au plus trois variables, est NP-complet tandis que 2-SAT peut être résolu en temps linéaire.
  • Le problème de coloration de graphe est NP-complet avec trois couleurs, mais polynomial avec deux couleurs.
  • Savoir s'il existe un circuit hamiltonien est NP-complet tandis que savoir s'il existe un circuit eulérien est dans P.

Certains problèmes NP, par exemple ceux exploités en cryptographie à clé publique, sont supposés être strictement entre P et NPC. En particulier, la méthode RSA repose sur la difficulté de la factorisation des entiers. Aucun algorithme polynomial n'est connu pour le résoudre, mais le problème appartient à NP \cap CoNP et n'est donc vraisemblablement pas NP-complet.

À l'opposé, il existe des problèmes de décision plus difficiles que les problèmes NP-complets. Certains problèmes sont indécidables, par exemple le problème de l'arrêt. Certains problèmes décidables nécessitent un espace exponentiel et ne sont donc pas dans NP, par exemple la comparaison des langages dénotés par deux expressions rationnelles dans lesquelles on autorise, en plus des opérations usuelles, l'opération carré[3] (c'est un problème complet dans EXPSPACE (en)).

Résolution

Méthodes exactes

La NP-complétude ne donne une idée de la difficulté d'un problème que dans le pire cas. Autrement dit, même si on ne sait pas résoudre rapidement toutes les instances d'un problème NP-complet, c'est parfois possible pour une partie d'entre elles.

Ainsi, des algorithmes par séparation et évaluation, non polynomiaux, peuvent avoir un temps d'exécution raisonnable pour des instances relativement grandes.

Si on a besoin de résoudre seulement une sous-classe des instances possibles, alors le problème peut devenir facile. Par exemple, la recherche de l'indépendant maximum (NP-complet) est possible en temps polynomial sur les graphes bipartis ou d'autres familles de graphes.

Dans certains cas, on sait démontrer que les instances aléatoires d'un problèmes NP-complets sont faciles. À titre d'exemple :

  • Le coloriage de graphe avec k couleurs (k ≥ 3) est NP-complet, mais les instances difficiles correspondent à des graphes peu denses. Ainsi, si on choisit un graphe à n sommet aléatoirement, de façon uniforme parmi les 2n(n-1)/2 possibles, la probabilité d'existence d'un k-coloriage tend vers 0 quand n augmente. De plus, un algorithme de coloriage glouton, explorant les sommets dans un ordre arbitraire, termine après avoir exploré O(1) sommets en moyenne[4].
  • À l'opposé, un graphe aléatoire contient un circuit hamiltonien avec une probabilité tendant vers 1 quand sa taille tend vers l'infini[5], et on peut trouver un tel circuit en temps probabiliste polynomial[6].

Enfin, l'approche de la complexité paramétrée consiste à identifier un paramètre qui, dans le cas où il reste petit, permet de résoudre rapidement le problème. En particulier les algorithmes FPT en un paramètre k permettent de résoudre un problème en temps proportionnel au produit d'une fonction quelconque de k et d'un polynôme en la taille de l'instance, ce qui fournit un algorithme polynomial quand k est fixé.

Méthodes approchées

Article détaillé : Algorithme d'approximation.

Lorsque les méthodes de résolution exactes ne sont pas applicables, des algorithmes d'approximations (ou à défaut des heuristiques) permettent de trouver des solutions approchées de l'optimum en un temps raisonnable pour un certain nombre de problèmes NP-complets.

  • Certains problèmes sont inapproximables, comme le problème du voyageur de commerce.
  • Par contre, le problème du voyageur de commerce restreint au cas où les distances satisfont l'inégalité triangulaire est approximable à un facteur 3/2 : il existe un algorithme polynomial qui calcule un chemin dont la longueur est au plus 3/2 fois plus grande que celle du chemin optimum.
  • D'autres problèmes admettent un schéma d'approximation polynomial (en), c'est-à-dire qu'ils sont approximables à un facteur (1+ε) en temps polynomial pour tout ε>0. C'est le cas du problème du sac à dos.

NP-complétude faible

Comme mentionné plus haut, il existe plusieurs manières de coder les instances d'un problème sous forme de mots (faits d’une suite finie de symboles d’un alphabet déterminé et fini). Choisir un encodage particulièrement long diminue artificiellement la complexité du problème, puisque celle-ci est exprimée en fonction de la taille de l'entrée.

En particulier, un nombre entier n peut être encodé sur log2 n symboles s’il est écrit en base 2 (ou une base supérieure) mais occupe n symboles s’il est écrit en unaire, ce qui est exponentiellement plus grand.

Les problèmes qu’on peut résoudre en temps polynomial lorsque leurs entrées sont codées en unaire sont appelés problèmes « NP-complets faibles ». Le problème du sac à dos et ses variantes appartiennent à cette catégorie. En effet, ils peuvent être résolus par programmation dynamique en temps polynomial en le nombre d'objets et la plus grande quantité intervenant dans l'entrée.

Par opposition, les problèmes qui restent NP-complets dans ce cas sont dits forts. C'est le cas de la plupart des autres problèmes cités dans cet article, comme SAT, CLIQUE, la coloration de graphe, etc.

Notes et références

  1. Stephen Cook, The complexity of theorem proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, pages 151–158, 1971.
  2. Pour être précis, la taille de la solution doit être bornée polynomialement en la taille de l'entrée, ce qui est toujours possible ici.
  3. Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.
  4. Une démonstration est donnée dans l'ouvrage de Wilf cité plus haut
  5. Jean-Paul Delahaye, L'intelligence et le calcul, Belin - Pour la Science, 2002, (ISBN 2-84245-040-X) (chapitre 1, « Les lois de tout ou rien »).
  6. D. Angluin and L. G. Valiant, Fast probabilistic algorithms for hamiltonian circuits and matchings, Journal of Computer and System Sciences, Volume 18, Issue 2, pp. 155-193, 1979.

Voir aussi

Articles connexes

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème NP-complet de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Probleme SAT — Problème SAT On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une valuation sur un ensemble de variables propositionnelles[1] telle qu… …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Probleme de la couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Probleme du voyageur de commerce — Problème du voyageur de commerce Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce …   Wikipédia en Français

  • Probleme de tournees de vehicules — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit …   Wikipédia en Français

  • Problème de livraison et de collecte — Problème de tournées de véhicules Figure illustrant un problème de tournées de véhicules avec un dépot central. Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d optimisation combinatoire. Il s agit …   Wikipédia en Français

  • Probleme de l'ensemble dominant — Problème de l ensemble dominant Le problème d ensemble dominant est un problème NP complet de la théorie des graphes. Sommaire 1 Définition 2 Exemple 3 NP complétude 3.1 Preuve …   Wikipédia en Français

  • Problème de l'ensemble dominant — Le problème d ensemble dominant est un problème NP complet de la théorie des graphes. Sommaire 1 Définition 2 Exemple 3 NP complétude 3.1 Preuve …   Wikipédia en Français

  • Probleme du nombre domatique — Problème du nombre domatique Le problème du nombre domatique est un problème NP complet de la théorie des graphes. Définition Une instance du problème du nombre domatique consiste en un graphe G avec un ensemble S de sommets et un ensemble A d… …   Wikipédia en Français

  • Problème 3SAT — Problème 3 SAT Le problème 3 SAT est un cas particulier du problème SAT quand la taille des clauses est exactement de 3. C est l un des 21 problèmes NP complets de Karp. Un exemple d instance de ce problème : E a 4 clauses, 5 littéraux v1,v2 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”