En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) 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. (Il permet de rapporter tous les problèmes de la classe NP à ce problème, mais n'est ni facile à vérifier, ni résoluble en un temps polynomial, quand il n'appartient pas à NP : NP-difficile \ NP-complet)
Pour tout problème NP-complet, bien qu’on puisse vérifier rapidement n’importe quelle solution proposée, on ne connaît pas de procédure pour concevoir une solution efficacement. C'est le cas, par exemple, du problème du voyageur de commerce ou de celui du problè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 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 ou utiliser des heuristiques pour trouver des solutions exactes.
Définition formelle
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 : La classe est l’ensemble des langages décidables en temps polynomial par une machine de Turing non déterministe. La classe est l’ensemble des langages décidables en temps polynomial par une machine de Turing déterministe. Elle est incluse dans .
Un langage est NP-difficile s’il existe une réduction polynomiale de tout langage à , c’est-à-dire une fonction (où est l’alphabet de ces langages), calculable en temps polynomial sur une machine de Turing déterministe, telle que : . Si de plus , alors le langage est NP-complet.
La classe des langages NP-complets est notée .
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 -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 « Passage de problème d'optimisation à problème de décision » de l’article sur la théorie de la complexité).
Histoire vignette|Diagramme d'Euler pour les problèmes NP-complets. Le concept de NP-complétude a été introduit en 1971 par Stephen Cook dans une communication intitulée The complexity of theorem-proving proceduresStephen Cook, The complexity of theorem proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, pages 151–158, 1971. (La complexité des procédures de démonstration de problèmes), bien que le mot « NP-complet » n'apparaisse pas explicitement dans l'article.
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À cette époque les échanges scientifiques entre le monde occidental et l'URSS étaient très ténus., 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 de milliers d'autres problèmes.
Preuves de NP-complétude
Pour démontrer la NP-complétude d'un nouveau problème , la méthode usuelle consiste à trouver un problème NP-complet déjà connu qui se réduit à . Cela suffit à démontrer que est NP-complet. En effet, pour tout , on a Π ≤ Π ≤ Π (la relation de réduction polynomiale ≤ 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 est satisfiable en posant v=vrai et v=faux. 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 efficacementPour ê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.. On définit la fonction de réduction f de la façon suivante. Soit une formule sous forme normale conjonctive. On définit comme étant le problème d'OLNE suivant : À chaque variable v correspond une variable x du système. De plus, on ajoute au système la contrainte 0 ≤ x ≤ 1. Pour chaque clause de la forme , avec des variables pas forcément distinctes, on ajoute au système la contrainte . Exemple Pour la formule , le système linéaire contient cinq inéquations : 0 ≤ x ≤ 1, 0 ≤ x ≤ 1, x + x ≥ 1, x + (1 - x) ≥ 1 et (1 - x) + (1 - x) ≥ 1.
On constate alors que si est satisfiable, alors en posant : x = 0 si v=faux, x = 1 si v=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 v telles que x = 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
Parmi les problèmes NP-complets notables, on peut citer : SAT et sa variante 3-SAT ; le problème du cycle hamiltonien et sa variante pondérée, le problème du voyageur de commerce ; la clique maximum (équivalent au stable maximum et à la couverture de sommets minimum) ; le problème ensemble dominant minimal ; les problèmes de coloration de graphe ; le problème du sac à dos.
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 : « 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 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 que 2-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 un circuit eulérien est dans P.
Certains problèmes dans 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 à NPco-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 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éAlbert R. Meyer et Larry 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. (c'est un problème complet dans EXPSPACE).
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 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 moyenneUne démonstration est donnée dans l'ouvrage de Wilf cité plus haut. ;