Classes P, NP et NP-Complétude

1. Complexité : De Décidable à Tractable

Un problème peut être décidable, mais l'algorithme qui le résout peut être si lent qu'il est inutilisable en pratique. Prenons l'exemple du problème de 3-coloration d'un graphe : on peut tester toutes les colorations possibles, mais le nombre de possibilités explose de manière exponentielle avec la taille du graphe. Cela nous amène à distinguer les algorithmes "raisonnables" des autres.

2. La Classe P : Les Problèmes Tractables

La convention que nous adoptons est de considérer qu'un problème est tractable s'il existe un algorithme pour le résoudre dont le temps d'exécution est polynomial en la taille de l'entrée. C'est ce qui définit la classe P.

Définition Formelle de P

Un problème de décision est dans la classe P s'il peut être résolu par une machine de Turing déterministe en un temps polynomial par rapport à la taille de l'entrée $n$. Formellement, on note :

où $\text{TIME}(f(n))$ est la classe des problèmes décidés par une machine de Turing en temps $O(f(n))$.

L'un des atouts de la classe P est sa robustesse : elle reste la même quel que soit le modèle de calcul déterministe raisonnable choisi (machine RAM, machine à k rubans, etc.), à un facteur polynomial près.

Exemples de problèmes dans P :

• Vérifier si un graphe est correctement coloré (BON-COLORIAGE).
• Trouver le plus court chemin entre deux points dans un graphe (algorithme de Dijkstra).
• Trier une liste de nombres.

3. La Classe NP : Les Problèmes Vérifiables

De nombreux problèmes importants ne semblent pas avoir d'algorithme polynomial connu. Cependant, ils partagent une propriété fascinante : si quelqu'un nous donne une solution, nous pouvons vérifier très rapidement (en temps polynomial) si cette solution est correcte. C'est l'intuition derrière la classe NP.

Pour une introduction claire en français à ce concept, je vous propose la vidéo suivante.

Définition Formelle de NP

Un problème de décision est dans la classe NP (pour Non-deterministic Polynomial time) s'il existe un vérificateur polynomial.
Plus formellement, un langage $L$ est dans NP s'il existe un algorithme déterministe $V$ (le vérificateur) et un polynôme $p$ tels que :

1. $V$ s'exécute en temps polynomial par rapport à la taille de l'entrée principale.
2. Pour toute instance $x$, on a : $x\in L$ si et seulement s'il existe une chaîne de caractères $c$ (le certificat) de taille polynomiale ($|c|\le p(|x|)$) telle que $V(x,c)$ accepte.

Exemples de problèmes dans NP :

• SAT (Satisfaisabilité) : Étant donnée une formule logique, existe-t-il une assignation des variables qui la rend vraie ? Le certificat est l'assignation.
• CHEMIN HAMILTONIEN : Existe-t-il un chemin qui visite chaque sommet d'un graphe exactement une fois ? Le certificat est la liste des sommets formant le chemin.
• 3-COLORABILITÉ : Peut-on colorier un graphe avec 3 couleurs sans que deux voisins aient la même couleur ? Le certificat est la couleur attribuée à chaque sommet.

Une définition équivalente (et historique, donnant son nom à la classe) est que NP est la classe des problèmes pouvant être résolus en temps polynomial par une machine de Turing non-déterministe. Ce modèle peut être vu comme une machine qui "devine" magiquement la bonne suite de choix menant à une solution.

La Question à un Million de Dollars : P = NP ?

Par définition, tout problème dans P est aussi dans NP. Si un problème peut être résolu en temps polynomial, il peut a fortiori être vérifié en temps polynomial (le certificat peut être ignoré).
La question fondamentale est de savoir si l'inclusion est stricte : $\mathbf{P}\subseteq \mathbf{NP}$.

Est-ce que $\mathbf{P}=\mathbf{NP}$ ?

Autrement dit, si une solution à un problème peut être vérifiée efficacement, peut-elle aussi être trouvée efficacement ? C'est le problème ouvert le plus célèbre de l'informatique. La plupart des chercheurs conjecturent que $\mathbf{P}\ne \mathbf{NP}$.

4. NP-Complétude : Les Problèmes les plus Difficiles de NP

Au sein de la classe NP, certains problèmes semblent être les "plus difficiles". Si l'un d'entre eux pouvait être résolu en temps polynomial, alors tous les problèmes de NP le pourraient aussi. Ces problèmes sont dits NP-complets.

Pour formaliser cette notion, nous avons besoin de l'outil de réduction polynomiale, qui est analogue à la réduction que nous avons évoquée pour l'indécidabilité, mais avec une contrainte de temps.

Réduction Polynomiale

Un problème $A$ se réduit en temps polynomial à un problème $B$, noté $A{\le }_{P}B$, s'il existe une fonction $f$ calculable en temps polynomial qui transforme toute instance $x$ de $A$ en une instance $f(x)$ de $B$, de sorte que :

Intuitivement, si $A{\le }_{P}B$, alors $B$ est "au moins aussi difficile" que $A$. Si on avait une solution efficace pour $B$, on en aurait une pour $A$.

Définitions de NP-difficulté et NP-complétude

1. Un problème $B$ est NP-difficile (NP-hard) si tout problème $A\in \mathbf{NP}$ se réduit en temps polynomial à $B$ ($\forall A\in \mathbf{NP},A{\le }_{P}B$).

   • Ces problèmes sont au moins aussi difficiles que n'importe quel problème de NP. Ils ne sont pas nécessairement dans NP eux-mêmes (le problème de l'arrêt est NP-difficile, par exemple).

2. Un problème $B$ est NP-complet (NP-complete) s'il satisfait deux conditions :

   • $B\in \mathbf{NP}$
   • $B$ est NP-difficile.

Les problèmes NP-complets sont donc les problèmes les plus difficiles de la classe NP.

Le professeur Demaine explique ces définitions et leurs implications de manière très claire.

Le Premier Problème NP-complet : Le Théorème de Cook-Levin

Comment prouver qu'un premier problème est NP-complet ? Il faudrait montrer que tous les problèmes de NP se réduisent à lui. C'est l'exploit monumental accompli indépendamment par Stephen Cook (1971) et Leonid Levin (1973).

Théorème (Cook-Levin) : Le problème SAT est NP-complet.

La preuve (très complexe) montre que tout calcul d'une machine de Turing non-déterministe peut être encodé en une formule SAT de taille polynomiale.

Une fois que nous avons ce premier problème, nous pouvons en trouver d'autres par "chaînage" : pour prouver qu'un problème $X$ est NP-complet, il suffit de :

1. Montrer que $X\in \mathbf{NP}$ (généralement facile).
2. Choisir un problème $Y$ que l'on sait déjà NP-complet (comme SAT).
3. Prouver que $Y{\le }_{P}X$.

Par transitivité des réductions, si $Y$ est NP-complet, et que $Y{\le }_{P}X$, alors $X$ est au moins aussi difficile que $Y$, et donc $X$ est aussi NP-difficile.

Les documents de préparation à l'Agrégation, comme celui de l'ENS Rennes, confirment que cette structure de raisonnement (définitions, théorème de Cook, stratégie de preuve par réduction) est au cœur de ce qui est attendu de vous.

Conclusion : Le Paysage de la Complexité

Cette leçon a déplacé notre perspective de la calculabilité (ce qui est calculable ou non) vers la complexité (ce qui est tractable ou non).

Points clés à retenir :

• La classe P contient les problèmes de décision résolubles en temps polynomial par une machine déterministe. Ce sont les problèmes considérés comme "tractables".
• La classe NP contient les problèmes dont une solution peut être vérifiée en temps polynomial. Elle est définie formellement via la notion de certificat et de vérificateur.
• La question $\mathbf{P}=\mathbf{NP}$ est le problème ouvert majeur de l'informatique théorique.
• Un problème est NP-difficile s'il est au moins aussi difficile que tous les problèmes de NP.
• Un problème est NP-complet s'il est NP-difficile et est lui-même dans NP. Ces problèmes sont les plus difficiles de NP.
• Le théorème de Cook-Levin a établi que SAT est le premier problème NP-complet, servant de point de départ pour prouver la NP-complétude d'une myriade d'autres problèmes par réduction polynomiale.

Prouver qu'un problème est NP-complet est une information capitale : cela suggère très fortement qu'il est inutile de chercher un algorithme exact et efficace pour le résoudre, et qu'il faut plutôt se tourner vers des heuristiques, des algorithmes d'approximation, ou des solutions pour des cas particuliers.

Dans la prochaine leçon, nous mettrons ces concepts en pratique en explorant le mécanisme de réduction polynomiale pour prouver qu'un autre problème fondamental, 3-SAT, est NP-complet.