Logique et ensemblesNotion · Glossaire
NP
NP est la classe des problèmes de décision dont chaque instance positive possède un certificat de taille polynomiale, vérifiable en temps polynomial par un algorithme déterministe. Elle formalise ainsi la distinction entre contrôler rapidement une solution proposée et la trouver rapidement. Savoir si ces deux tâches sont toujours aussi faciles revient à demander si P = NP, question encore ouverte.
Sommaire
Ce que vous allez apprendre
- Identifier le rôle d'un certificat et d'un vérificateur polynomial.
- Suivre la vérification complète d'une tournée proposée.
- Distinguer P, NP, NP-complet et NP-difficile.
- Formuler exactement la question P = NP sans la présenter comme résolue.
En clair
Imaginez une tournée passant par plusieurs villes. Trouver un trajet assez court peut demander d'examiner une foule de possibilités. En revanche, si quelqu'un propose un trajet, vous pouvez contrôler qu'il passe par chaque ville, additionner ses longueurs et comparer le total à une limite donnée.
La classe NP rassemble les problèmes de décision pour lesquels ce contrôle reste rapide quand la taille des données augmente. « Rapide » signifie ici que le nombre d'étapes est borné par un polynôme de cette taille.
Définition
NP est une classe de problèmes de décision, c'est-à-dire de questions dont la réponse est oui ou non. Pour une instance de taille notée n, une réponse « oui » doit pouvoir être accompagnée d'un certificat dont la longueur est bornée par un polynôme en n. Un algorithme déterministe, appelé vérificateur, doit ensuite contrôler ce certificat en un nombre d'étapes lui aussi polynomial en n.
Le mot « non déterministe » vient d'une formulation équivalente : une machine abstraite peut choisir un certificat favorable, puis le vérifier en temps polynomial. Cette définition n'affirme pas qu'un algorithme déterministe sait trouver rapidement le certificat. Elle exige seulement qu'un certificat proposé pour une instance positive soit court et rapidement contrôlable.
La classe P regroupe les problèmes de décision directement résolus en temps polynomial par un algorithme déterministe. Toute solution calculée peut aussi être contrôlée, donc . On ignore si l'inclusion est stricte. La question demande précisément si la recherche d'une réponse peut toujours être rendue aussi efficace, au sens polynomial, que sa vérification.
Un exemple, pas à pas
Considérons la version décisionnelle d'une petite tournée. Les villes sont A, B et C. Le circuit proposé est A–B–C–A. Les longueurs annoncées sont 4 pour A–B, 6 pour B–C et 5 pour C–A. La limite à ne pas dépasser est 16. Le circuit proposé joue le rôle de certificat.
1. Vérifier que A, B et C figurent chacune une fois avant le retour à A.
2. Lire les trois longueurs du circuit proposé.
3. Calculer le coût total : .
4. Comparer le total à la limite : .
2. Lire les trois longueurs du circuit proposé.
3. Calculer le coût total : .
4. Comparer le total à la limite : .
La réponse est donc « oui » pour ce certificat. Le contrôle se refait en suivant trois arêtes et en additionnant trois nombres. Cet exemple montre la vérification d'une proposition ; il ne fournit pas une méthode pour découvrir le meilleur circuit parmi tous les circuits possibles.
En pratique
Face à un problème de décision, on cherche d'abord la forme d'un certificat pour une réponse « oui ». Pour une tournée, ce certificat est une liste ordonnée de villes ; le geste concret consiste à contrôler les visites, la validité du circuit et de ses arêtes dans l'instance, puis son coût.
On mesure ensuite le travail du vérificateur en fonction de la taille de l'entrée. Si ce travail est borné par un polynôme et si le certificat reste de longueur polynomiale, cette caractérisation permet d'établir l'appartenance à NP. Une simple vérification rapide sur quelques exemples ne suffit pas.
Lorsqu'un problème demande une valeur optimale plutôt qu'une réponse oui ou non, on formule une question à seuil, comme « existe-t-il une tournée de coût au plus 16 ? ». Cette version décisionnelle est celle à laquelle la classe NP s'applique directement.
À ne pas confondre
NP et P. Dans P, un algorithme déterministe produit la réponse en temps polynomial. Dans NP, la condition porte sur la vérification d'un certificat de réponse « oui ». Pour la tournée proposée, le vérificateur contrôle les visites requises et l'existence des arêtes, puis additionne les longueurs et compare le total à la limite, sans montrer que l'on sait trouver rapidement un circuit convenable.
NP et NP-complet. NP est toute la classe des problèmes ainsi vérifiables. Un problème NP-complet appartient à NP et représente aussi la difficulté de tous les problèmes de NP au moyen de transformations polynomiales. Appartenir à NP ne suffit donc pas à être NP-complet.
NP-complet et NP-difficile. Un problème NP-difficile porte au moins la difficulté des problèmes de NP, mais il n'est pas nécessairement un problème de décision appartenant à NP. Le critère qui tranche est l'appartenance à NP, exigée pour « NP-complet » et non pour « NP-difficile ».
Limites et pièges
« Vérifiable rapidement » ne signifie pas « facile à résoudre ». Le symptôme du piège est le passage direct du contrôle d'un certificat à la découverte de ce certificat. Il faut analyser séparément l'algorithme de vérification et l'algorithme de résolution.
Le temps polynomial dépend de la taille de l'entrée. Un programme rapide sur trois villes ne prouve rien sur sa croissance générale. Il faut exprimer son nombre d'étapes en fonction de la taille n et établir une borne polynomiale valable pour toutes les instances.
La définition vise les certificats des réponses « oui ». Pour établir qu'une instance est dans NP, il n'est pas demandé par cette définition de fournir un certificat analogue pour chaque réponse « non ». Il faut formuler clairement la question de décision et identifier les instances positives.
L'égalité P = NP reste une question ouverte. Présenter l'une des deux réponses comme acquise contredit l'état décrit par la notion. Il faut distinguer les inclusions démontrées, comme , de l'égalité encore inconnue.
Pour aller plus loin
classe de complexité P — Pour préciser ce que signifie résoudre un problème de décision en temps polynomial et situer l'inclusion de P dans NP.
algorithme — Pour revenir à la notion de procédure déterministe qui intervient dans la résolution et dans la vérification.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres