classe de complexité NP

Imaginez une grille de contraintes accompagnée d'une proposition de réponse. Trouver cette réponse peut demander beaucoup d'essais, mais la contrôler peut être rapide : il suffit de tester chaque contrainte.

La classe NP rassemble les problèmes de décision de ce genre. Pour chaque instance dont la réponse est « oui », au moins un certificat permet de convaincre un vérificateur en un nombre d'étapes polynomial par rapport à la taille des données et du certificat. Si la réponse est « non », aucun certificat ne doit pouvoir convaincre ce vérificateur. NP signifie « temps polynomial non déterministe » ; cela ne veut pas dire « non polynomial ».

NP est une classe de problèmes de décision, c'est-à-dire de questions dont la réponse est « oui » ou « non ». Un problème appartient à NP lorsqu'il existe un vérificateur déterministe tel que chaque instance positive possède au moins un certificat de longueur polynomiale qu'il accepte, tandis que, pour une instance négative, il n'accepte aucun certificat. Son temps d'exécution est polynomial en la taille de l'instance et du certificat. La taille de l'instance, et non sa valeur numérique brute, sert de mesure.

La classe P regroupe les problèmes de décision résolubles en temps polynomial par un algorithme déterministe. Toute solution calculée rapidement peut aussi être contrôlée rapidement, donc P ⊆ NP. On ignore si l'inclusion est stricte : l'affirmation P ≠ NP reste une conjecture, tandis que l'égalité P = NP demeure une possibilité non écartée.

Un problème est NP-complet s'il appartient à NP et si tout problème de NP peut lui être transformé par une réduction calculable en temps polynomial. Ces problèmes concentrent ainsi la difficulté de la classe : un algorithme polynomial pour l'un d'eux entraînerait P = NP. Le problème SAT, qui demande si une formule booléenne admet une affectation vraie, est NP-complet d'après le théorème de Cook-Levin.

Considérons une instance de SAT composée de trois contraintes : x ou y ; non x ou z ; non y ou non z. Le certificat proposé affecte les valeurs vrai à x, faux à y et vrai à z.

1. Remplaçons x et y dans la première contrainte : « vrai ou faux » vaut vrai.

2. La deuxième devient « faux ou vrai », donc elle vaut vrai.

3. La troisième devient « vrai ou faux », donc elle vaut vrai.

Les trois contraintes étant vraies, le certificat prouve que cette instance a pour réponse « oui ». Le schéma de contrôle rend visible le travail du vérificateur : il lit l'affectation, évalue chaque contrainte, puis accepte seulement si toutes réussissent. Le contrôle est refaisable en reprenant les trois substitutions, sans chercher une autre affectation.

Pour montrer qu'un problème appartient à NP, on décrit le certificat fourni pour une instance positive, puis un vérificateur polynomial. Une simple intuition de contrôle rapide ne suffit pas : il faut aussi borner la longueur du certificat et le temps de vérification en fonction de la taille de l'entrée.

Pour établir qu'un problème est NP-complet, l'appartenance à NP est complétée par une réduction polynomiale depuis un problème déjà NP-complet. Une preuve directe de résolution polynomiale serait préférable si l'on dispose effectivement d'un tel algorithme, car elle placerait le problème dans P.

Face à une proposition de solution, le bon geste est de séparer recherche et vérification. Dans l'exemple SAT, tester l'affectation donnée suffit ; énumérer toutes les affectations ne devient nécessaire que si aucune méthode plus efficace n'est connue pour chercher une solution.

NP et « non polynomial ». Les lettres NP abrègent « temps polynomial non déterministe ». Le critère testable est l'existence d'une vérification polynomiale des certificats positifs, et non la preuve qu'aucun algorithme polynomial ne peut résoudre le problème.

NP-complet et NP-difficile. Un problème NP-complet appartient à NP et reçoit une réduction polynomiale de tout problème de NP. Dire seulement qu'un problème est au moins aussi difficile que tous ceux de NP ne suffit pas à garantir qu'il est lui-même dans NP.

Vérifier et trouver. Pour l'instance SAT proposée, contrôler x vrai, y faux et z vrai exige seulement trois tests. Trouver cette affectation sans certificat est une autre tâche ; l'efficacité de la première ne prouve pas celle de la seconde.

Le certificat concerne les réponses positives. La définition de NP garantit un certificat court pour une instance dont la réponse est « oui ». Elle ne garantit pas, à elle seule, un certificat analogue pour chaque réponse « non ». Il faut donc identifier clairement quel verdict le certificat atteste.

Polynomial signifie polynomial en la taille de l'entrée. Pour un entier écrit en binaire, cette taille est son nombre de bits, pas l'entier lui-même. Une analyse qui emploie la mauvaise mesure peut annoncer à tort un temps polynomial ; il faut expliciter l'encodage et compter les symboles lus.

Le sens d'une réduction est décisif. Pour transmettre la difficulté d'un problème NP-complet connu vers un nouveau problème, on transforme le problème connu en nouveau problème. Inverser cette transformation montre au mieux que l'ancien problème peut traiter le nouveau ; cela n'établit pas la NP-difficulté visée.

P contre NP reste ouvert. Ni P = NP ni P ≠ NP ne peut être présenté comme un résultat acquis. Lorsqu'un raisonnement utilise l'une de ces affirmations, il faut la signaler comme hypothèse ; la conjecture usuelle est P ≠ NP.

Temps polynomial précise la borne d'efficacité utilisée pour définir le vérificateur et les réductions de NP.

complexité temporelle donne le cadre permettant de relier le nombre d'opérations à la taille de l'entrée.