L'essentiel à connaître
$\mathrm{P}$ regroupe les problèmes de décision (réponse oui ou non) qu'un algorithme résout en temps polynomial en la taille de l'entrée. $\mathrm{NP}$ regroupe ceux dont une réponse « oui » se vérifie en temps polynomial grâce à un certificat, une solution proposée de taille polynomiale. Exemple : pour SAT (une formule booléenne à $n$ variables peut-elle être rendue vraie ?), essayer les $2^n$ affectations des variables (vrai ou faux) explose, mais vérifier une affectation proposée demande un seul passage sur la formule.
La question « $\mathrm{P} = \mathrm{NP}$ ? » demande donc si vérifier vite permet toujours de trouver vite. C'est l'un des sept problèmes du prix du millénaire du Clay Mathematics Institute, et Stephen Cook en a rédigé la description officielle. La plupart des spécialistes pensent que $\mathrm{P} \neq \mathrm{NP}$, mais personne ne sait le démontrer.
$\mathrm{NP}$ veut dire « polynomial non déterministe » : la classe a d'abord été définie avec des machines de Turing non déterministes, qui ont plusieurs coups possibles à chaque étape. Jamais « non polynomial » : un algorithme polynomial décide sans regarder le certificat, donc $\mathrm{P} \subseteq \mathrm{NP}$. On sait aussi que $\mathrm{NP} \subseteq \mathrm{PSPACE}$ (mémoire polynomiale), sans qu'aucune des deux inclusions soit prouvée stricte.
Définition : $L_1 \le_p L_2$ ($L_1$ se réduit polynomialement à $L_2$) s'il existe une fonction $f$ calculable en temps polynomial telle que $x \in L_1 \iff f(x) \in L_2$. Un problème $L$ est $\mathrm{NP}$-difficile si tout problème de $\mathrm{NP}$ se réduit à $L$, et $\mathrm{NP}$-complet s'il est en plus dans $\mathrm{NP}$.
Cook a montré en 1971 que SAT et 3-SAT (formules en clauses de trois littéraux, variables ou négations de variables) sont $\mathrm{NP}$-complets ; Leonid Levin a obtenu indépendamment un résultat voisin. Le problème de l'arrêt (une machine de Turing donnée s'arrête-t-elle sur une entrée donnée ?) est $\mathrm{NP}$-difficile mais indécidable : aucun algorithme ne le résout, il est donc hors de $\mathrm{NP}$. Savoir si un entier est composé est dans $\mathrm{P}$ (Agrawal, Kayal et Saxena, article publié en 2004), alors qu'aucun algorithme polynomial n'est connu pour factoriser.
Propriété : si $L_1 \le_p L_2$ et $L_2 \in \mathrm{P}$, alors $L_1 \in \mathrm{P}$. Un seul problème $\mathrm{NP}$-complet dans $\mathrm{P}$ donnerait donc $\mathrm{P} = \mathrm{NP}$. Pour prouver qu'un problème $L$ de $\mathrm{NP}$ est $\mathrm{NP}$-complet, tu réduis vers lui un problème $\mathrm{NP}$-complet connu : $3\text{-SAT} \le_p L$.
Piège classique : la taille de l'entrée se mesure en chiffres, pas en valeur. Si un nombre $T$ de l'entrée a $k$ chiffres, $T \ge 10^{k-1}$ : un temps proportionnel à $T$ est donc exponentiel en $k$. Un tel algorithme, polynomial en la valeur des nombres mais pas en leur longueur, est dit pseudo-polynomial.
Quiz : teste tes connaissances
Dix questions, de la plus simple à la plus piégeuse : méfie-toi surtout des trois dernières.
Question 1 : Que veut dire le nom $\mathrm{NP}$ ?
Réponse : C. $\mathrm{NP}$ rassemble ce qu'une machine de Turing non déterministe décide en temps polynomial, ce qui revient à vérifier un certificat en temps polynomial. A est le contresens classique : comme $\mathrm{P} \subseteq \mathrm{NP}$, $\mathrm{NP}$ contient aussi tous les problèmes faciles.
Question 2 : Pour montrer que SAT est dans $\mathrm{NP}$, quel certificat donne-t-on pour une formule à $n$ variables ?
Réponse : D. Ce certificat tient en $n$ valeurs, et on l'évalue sur la formule en temps polynomial. A est faux : $2^n$ lignes ne forment pas un certificat de taille polynomiale.
Question 3 : Un problème $L$ est $\mathrm{NP}$-complet quand :
Réponse : B. Il faut les deux conditions : être dans $\mathrm{NP}$ et être $\mathrm{NP}$-difficile. D ne donne que la seconde, c'est-à-dire la définition de $\mathrm{NP}$-difficile ; C met la réduction dans le mauvais sens.
Question 4 : Quelqu'un résout 3-SAT en temps $O(n^3)$, avec $n$ la taille de la formule. Qu'en conclure ?
Réponse : C. Pour $L \in \mathrm{NP}$, la réduction de $L$ vers 3-SAT suivie de l'algorithme cubique reste polynomiale, donc $L \in \mathrm{P}$. A est faux : être $\mathrm{NP}$-complet ne veut pas dire « prouvé difficile », c'est une affaire de réductions.
Question 5 : On sait que $L_1 \le_p L_2$. Quelle déduction est correcte ?
Réponse : A. C'est la contraposée de la propriété « si $L_2 \in \mathrm{P}$, alors $L_1 \in \mathrm{P}$ ». Le piège D renverse le sens : tout problème de $\mathrm{P}$ se réduit au problème de l'arrêt (on calcule la réponse, puis on renvoie une machine qui s'arrête ou qui boucle), qui n'est ni dans $\mathrm{P}$ ni dans $\mathrm{NP}$. Le même exemple écarte B et C.
Question 6 : Le problème de l'arrêt est $\mathrm{NP}$-difficile. Qu'est-ce qui l'empêche d'être $\mathrm{NP}$-complet ?
Réponse : D. Tout problème de $\mathrm{NP}$ est décidable, puisqu'on peut essayer les certificats un par un ; le problème de l'arrêt ne l'est pas, comme l'a montré Turing. A est le piège : aucun algorithme ne le résout, même en temps exponentiel.
Question 7 : Le problème « l'entier $a$ est-il composé ? » est dans $\mathrm{NP}$ : un diviseur $b$ de $a$ tel que $1 < b < a$ sert de certificat. Que sait-on de plus ?
Réponse : B. Agrawal, Kayal et Saxena ont prouvé que tester si un entier est premier, donc aussi s'il est composé, se fait en temps polynomial (article publié en 2004). D est le piège : ce résultat a tranché la question, sans donner de méthode pour factoriser.
Question 8 : Tu as montré que ton problème $L$ est dans $\mathrm{NP}$. Quelle réduction construis-tu pour prouver qu'il est $\mathrm{NP}$-complet ?
Réponse : A. Tout problème de $\mathrm{NP}$ se réduit à 3-SAT, donc, par composition des réductions, à $L$. B est l'erreur de sens classique : elle ne prouve rien, puisque tout problème de $\mathrm{NP}$ se réduit déjà à 3-SAT.
Question 9 : La somme de sous-ensemble (des entiers positifs écrits en décimal et une cible $T$ : une partie de ces entiers a-t-elle pour somme $T$ ?) est $\mathrm{NP}$-complète. Une programmation dynamique sur les sommes atteignables la résout en $O(nT)$ pour $n$ entiers. Qu'en conclure ?
Réponse : D. Si $T$ a $k$ chiffres, $T \ge 10^{k-1}$ : la borne $nT$ est exponentielle en $k$, et l'algorithme n'est que pseudo-polynomial. A est le piège : « polynomial » se mesure en la longueur de l'écriture des nombres, pas en leur valeur. C ne change rien : $T$ reste exponentiel en son nombre de bits.
Question 10 : Laquelle de ces affirmations est un théorème démontré ?
Réponse : C. Les deux inclusions sont prouvées ; pour la seconde, on essaie les certificats un par un en réutilisant la même mémoire. Aucune n'est prouvée stricte, d'où le faux D. A et B entraîneraient $\mathrm{P} \neq \mathrm{NP}$, qui reste une conjecture.
Sources
Stephen Cook, « The P versus NP Problem », description officielle du problème pour le Clay Mathematics Institute (en anglais).
Clay Mathematics Institute, « Millennium Prize Problems », la liste des sept problèmes du prix du millénaire (en anglais).