Movatterモバイル変換

[0]ホーム
URL:

Aller au contenu
Wikipédial'encyclopédie libre
Rechercher

Problème NP-complet

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuisNP-complet)
Page d’aide sur l’homonymie

Pour les articles homonymes, voirNP etNPC.

Page d’aide sur l’homonymie

Ne doit pas être confondu avec unproblème NP-difficile.

Enthéorie de la complexité, unproblème NP-complet ouproblème NPC (c'est-à-dire un problèmecomplet pour la classeNP) est unproblème de décision vérifiant les propriétés suivantes :

  • il est possible de vérifier une solution efficacement (entemps 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 uneréduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP.

Un problèmeNP-difficile est un problème qui remplit la seconde condition, et donc peut être dans une classe de problème plus large et donc plus difficile que la classe NP.

Bien qu'on puissevérifier rapidement toute solution proposée d'un problème NP-complet, on ne sait pas entrouver efficacement. C'est le cas, par exemple, duproblème du voyageur de commerce ou de celui duproblème du sac à dos.

La plupart des algorithmes connus pour résoudre des problèmes NP-complets ont un temps d'exécution exponentiel en fonction de la taille des données d'entrée dans le pire des 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 résoudre un quelconque des problèmes NP-complets, 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 desproblèmes non résolus en mathématiques les plus importants à ce jour.

En pratique, lesinformaticiens et lesdé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 desalgorithmes d'approximation ou utiliser desheuristiques pour trouver des solutions exactes.

Définition formelle

[modifier |modifier le code]
Les classesP{\displaystyle P} etNPC{\displaystyle NPC} sont incluses dansNP{\displaystyle NP}. SiP≠NP{\displaystyle P\not =NP}, elles sont disjointes et il existe desproblèmes NP-intermédiaires, i.e. dansNP−(NPC∪P){\displaystyle NP-(NPC\cup P)} (représenté ici par la section médiane de l'ovoïdeNP{\displaystyle NP}).

Unproblème de décision peut être décrit mathématiquement par unlangage formel, dont les mots correspondent aux instances du problème pour lesquelles la réponse estoui.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Σ{\displaystyle \Sigma }.

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

UnlangageL{\displaystyle L\,} estNP-difficile s’il existe uneréduction polynomiale de tout langageL′∈NP{\displaystyle L'\in NP\,} àL{\displaystyle L\,}, c’est-à-dire une fonctionf:Σ∗↦Σ∗{\displaystyle f:\Sigma ^{*}\mapsto \Sigma ^{*}\,} (oùΣ{\displaystyle \Sigma \,} est l’alphabet de ces langages), calculable en temps polynomial sur une machine de Turing déterministe, telle que :

∀w∈Σ∗,w∈L′⇔f(w)∈L{\displaystyle \forall w\in \Sigma ^{*},w\in L'\Leftrightarrow f(w)\in L\,}.

Si de plusL∈NP{\displaystyle L\in NP\,}, alors lelangageL{\displaystyle L\,} estNP-complet.

La classe des langages NP-complets est notéeNPC{\displaystyle NPC\,}.

On dit qu’unproblè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 codageraisonnable du problème vers le langage considéré (voir la sectionNP-complétude faible).

Parabus de langage, on qualifie souvent de « NP-complets » desproblèmes d'optimisation et non des problèmes de décision. Ainsi, on dira que leproblème du voyageur de commerce, qui consiste à trouver un plus courtcircuit passant une seule fois par chacun des sommets d'ungraphe connexe fini, estNP{\displaystyle 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 la recherche à la décision » de l’article sur la théorie de la complexité).

Histoire

[modifier |modifier le code]
Diagramme d'Euler pour les problèmes NP-complets.

Le concept de NP-complétude a été introduit en 1971 parStephen Cook dans une communication intituléeThe 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 chercheurs présents pour savoir si les problèmes NP-complets pouvaient être résolus en temps polynomial surmachine 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.[réf. souhaitée]

Laquestion de savoir si P = NP n'est toujours pas résolue. Elle fait partie desproblè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 dedollars. 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 parLeonid Levin en URSS[2], est maintenant connu sous le nom dethéorème de Cook-Levin. Ce théorème affirme qu'il existe un problème NP-complet. Cook a choisi leproblè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 des21 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

[modifier |modifier le code]

Pour démontrer la NP-complétude d'un nouveau problèmeΠ1∈NP{\displaystyle \Pi _{1}\in NP}, la méthode usuelle consiste à trouver un problème NP-completΠ2{\displaystyle \Pi _{2}} déjà connu qui se réduit àΠ1{\displaystyle \Pi _{1}}. Cela suffit à démontrer queΠ1{\displaystyle \Pi _{1}} est NP-complet. En effet, pour toutΠ∈NP{\displaystyle \Pi \in NP}, on a Π ≤P Π2 ≤P Π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 deSAT, 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 sousforme normale conjonctive est satisfiable.

Exemple
(v1∨v2)∧(v1∨¬v2)∧(¬v1∨¬v2){\displaystyle (v_{1}\lor v_{2})\land (v_{1}\lor \lnot v_{2})\land (\lnot v_{1}\lor \lnot v_{2})} est satisfiable en posantv1=vrai etv2=faux.
(v1∨v2)∧(v1∨¬v2)∧(¬v1){\displaystyle (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[3].On définit la fonction de réductionf de la façon suivante. Soitϕ{\displaystyle \phi } une formule sous forme normale conjonctive.On définitf(ϕ){\displaystyle f(\phi )} comme étant le problème d'OLNE suivant :

Exemple
Pour la formule(v1∨v2)∧(v1∨¬v2)∧(¬v1∨¬v2){\displaystyle (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ϕ{\displaystyle \phi } est satisfiable, alors en posant :

  • xi = 0 sivi=faux,
  • xi = 1 sivi=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 variablesvi telles quexi = 1. Ainsi, la fonctionf 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

[modifier |modifier le code]
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 desproblèmes de décision. Cependant, les problèmes de décision associés à un problème d'optimisation, typiquement de la forme : « 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

[modifier |modifier le code]

Parfois, une modification apparemment 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 que2-SAT peut être décidé 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 uncircuit eulérien est dans P.

Certains problèmes dans NP, par exemple ceux exploités encryptographie à clé publique, sont supposés être strictement entre P et NPC. En particulier, la méthodeRSA repose sur la difficulté de lafactorisation des entiers. Aucun algorithme polynomial n'est connu pour le résoudre, mais le problème appartient à NP∩{\displaystyle \cap }co-NP 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 sontindécidables, par exemple leproblème de l'arrêt. Certains problèmes décidables nécessitent unespace exponentiel et ne sont donc pas dans NP, par exemple la comparaison des langages dénotés par deuxexpressions rationnelles dans lesquelles on autorise, en plus des opérations usuelles, l'opérationcarré[4] (c'est un problème complet dansEXPSPACE).

Résolution

[modifier |modifier le code]

Méthodes exactes

[modifier |modifier le code]

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 parsé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 lesgraphes bipartis ou d'autres familles de graphes.

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

  • Le coloriage de graphe aveck 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çonuniforme parmi les 2n(n-1)/2 possibles, la probabilité d'existence d'unk-coloriage tend vers 0 quandn augmente. De plus, un algorithme de coloriageglouton, explorant les sommets dans un ordre arbitraire, termine après avoir exploréO(1) sommets en moyenne[5] ;
  • À l'opposé, ungraphe aléatoire contient uncircuit hamiltonien avec une probabilité tendant vers 1 quand sa taille tend vers l'infini[6], et on peut trouver un tel circuit en temps probabiliste polynomial[7].

Enfin, l'approche de lacomplexité 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 lesalgorithmes FPT en un paramètrek permettent de résoudre un problème en temps proportionnel au produit d'une fonction quelconque dek et d'un polynôme en la taille de l'instance, ce qui fournit un algorithme polynomial quandk est fixé.

Méthodes approchées

[modifier |modifier le code]
Article détaillé :Algorithme d'approximation.

Lorsque les méthodes de résolution exactes ne sont pas applicables, desalgorithmes d'approximations (ou à défaut desheuristiques) 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 leproblè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 unschéma d'approximation polynomial, c'est-à-dire qu'ils sont approximables à un facteur (1+ε) en temps polynomial pour tout ε > 0. C'est le cas duproblème du sac à dos.

NP-complétude faible

[modifier |modifier le code]

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 entiern peut être encodé sur log2n symboles s’il est écrit enbase 2 (ou une base supérieure) mais occupen symboles s’il est écrit enunaire, 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 ». Leproblème du sac à dos et ses variantes appartiennent à cette catégorie. En effet, ils peuvent être résolus parprogrammation 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 ditsforts. 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

[modifier |modifier le code]
  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. ↑À cette époque les échanges scientifiques entre le monde occidental et l'URSS étaient très ténus.
  3. ↑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.
  4. ↑Albert R. Meyer etLarry 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.
  5. ↑Une démonstration est donnée dans l'ouvrage de Wilf cité plus haut.
  6. ↑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 »).
  7. ↑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

[modifier |modifier le code]

Articles connexes

[modifier |modifier le code]

Liens externes

[modifier |modifier le code]
v ·m
Classes de complexité
(liste)
Classes classiques
Classes randomisées et quantiques
Autres
Classes de fonctions calculables
Hiérarchies
Familles de classes
Théorèmes et outils
Théorèmes structurels
Outils et réductions
Approches non-standard
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Problème_NP-complet&oldid=223701775 ».
Catégories :
Catégories cachées :
[8]ページ先頭
©2009-2025 Movatter.jp