Problème NP-complet

Les classes ${\displaystyle P}$ et ${\displaystyle NPC}$ sont incluses dans ${\displaystyle NP}$. Si ${\displaystyle P\not =NP}$, elles sont disjointes et il existe des problèmes NP-intermédiaires, i.e. dans${\displaystyle NP-(NPC\cup P)}$ (représenté ici par la section médiane de l'ovoïde ${\displaystyle NP}$).

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 ${\displaystyle \Sigma }$.

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 ${\displaystyle NP\,}$ est l’ensemble des langages décidables en temps polynomial par une machine de Turing non déterministe.
• La classe ${\displaystyle P\,}$ est l’ensemble des langages décidables en temps polynomial par une machine de Turing déterministe. Elle est incluse dans ${\displaystyle NP\,}$.

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 ${\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 l’existence à la décision » de l’article sur la théorie de la complexité).

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 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 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[2], 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.

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

${\displaystyle (v_{1}\lor v_{2})\land (v_{1}\lor \lnot v_{2})\land (\lnot v_{1}\lor \lnot v_{2})}$ est satisfiable en posant v₁=vrai et v₂=faux.

${\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éduction f de la façon suivante. Soit ${\displaystyle \phi }$ une formule sous forme normale conjonctive. On définit ${\displaystyle f(\phi )}$ comme étant le problème d'OLNE suivant :

• À chaque variable v_i correspond une variable x_i du système. De plus, on ajoute au système la contrainte 0 ≤ x_i ≤ 1.
• Pour chaque clause de la forme ${\displaystyle v_{1}\lor \dots \lor v_{k}\lor \lnot v_{k+1}\lor \dots \lor \lnot v_{n}}$, avec ${\displaystyle v_{1},\dots ,v_{n}}$ des variables pas forcément distinctes, on ajoute au système la contrainte ${\displaystyle x_{1}+\dots +x_{k}+(1-x_{k+1})+\dots +(1-x_{n})\geq 1}$.

Exemple

Pour la formule ${\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 ≤ x₁ ≤ 1, 0 ≤ x₂ ≤ 1, x₁ + x₂ ≥ 1, x₁ + (1 - x₂) ≥ 1 et (1 - x₁) + (1 - x₂) ≥ 1.

On constate alors que si ${\displaystyle \phi }$ est satisfiable, alors en posant :

• x_i = 0 si v_i=faux,
• x_i = 1 si v_i=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_i telles que x_i = 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.

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

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.

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 log₂ 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.