problème NP-complet

Imaginez une grille logique dont une case cochée constitue une réponse proposée. Contrôler cette réponse peut demander peu d'étapes, alors que trouver la bonne combinaison parmi toutes les possibilités semble bien plus difficile.

Un problème NP-complet réunit deux idées. Une réponse positive accompagnée d'un certificat se vérifie en temps polynomial. De plus, tout problème de la classe NP peut être traduit en ce problème sans explosion non polynomiale du temps de traduction. Résoudre rapidement un seul problème NP-complet donnerait donc une méthode rapide pour tous les problèmes de NP.

Un problème NP-complet est d'abord un problème de décision : chaque instance appelle une réponse « oui » ou « non ». Il appartient à la classe NP lorsque, pour chaque instance dont la réponse est « oui », il existe un certificat dont la longueur est bornée polynomialement par la taille de l'instance et qui peut être vérifié par un algorithme en temps polynomial. Cette propriété concerne la vérification d'un certificat, pas nécessairement sa découverte.

Le problème doit aussi être NP-difficile. Cela signifie que tout problème de NP se transforme en lui au moyen d'une réduction calculable en temps polynomial, tout en conservant la réponse « oui » ou « non ». Les deux conditions sont indispensables : appartenir à NP ne suffit pas, et être NP-difficile ne garantit pas à lui seul l'appartenance à NP.

Stephen Cook a établi en 1971 la NP-complétude du problème de satisfiabilité SAT. Le sac à dos, la clique et la version décisionnelle du voyageur de commerce sont aussi des exemples canoniques. Si un algorithme polynomial résolvait un seul problème NP-complet, les réductions donneraient des algorithmes polynomiaux pour tous les problèmes de NP. La question équivalente de savoir si P = NP reste ouverte.

Considérons une instance de SAT. Les variables logiques sont nommées x, y et z. La formule comporte trois clauses, reliées par « et » : $(x\vee y)\wedge (\mathrm{\neg }x\vee z)\wedge (\mathrm{\neg }y\vee \mathrm{\neg }z)(x\; \backslash lor\; y)\; \backslash land\; (\backslash lnot\; x\; \backslash lor\; z)\; \backslash land\; (\backslash lnot\; y\; \backslash lor\; \backslash lnot\; z)$. Le certificat proposé attribue vrai à x, faux à y et vrai à z.

1. Dans la première clause, x est vrai et y est faux. L'alternative « x ou y » est donc vraie.

2. Dans la deuxième clause, la négation de x est fausse, mais z est vrai. L'alternative reste vraie.

3. Dans la troisième clause, la négation de y est vraie et la négation de z est fausse. Cette clause est vraie.

4. Les trois clauses étant vraies simultanément, la formule entière est vraie. Le certificat prouve donc que cette instance de SAT reçoit la réponse « oui ».

Le contrôle est refaisable en reprenant les trois clauses une à une. Cet exemple montre la vérification rapide d'un certificat donné ; il ne fournit pas une méthode rapide pour trouver une affectation satisfaisante dans toute instance.

Pour classer un problème de décision, on cherche séparément un vérificateur polynomial et une réduction polynomiale depuis un problème déjà connu comme NP-complet. Si le problème produit une valeur optimale plutôt qu'un verdict oui/non, on formule d'abord sa version décisionnelle.

Pour prouver qu'un problème est NP-difficile, on transforme un problème connu vers le problème étudié. Une transformation dans le sens inverse ne donne pas le verdict recherché ; le sens de la réduction doit donc être contrôlé explicitement.

Face à une instance concrète, la NP-complétude décrit le pire cas général. Lorsque les données sont petites ou possèdent une structure particulière, une recherche exhaustive, une méthode spécialisée ou une approximation peut rester préférable selon le résultat attendu.

NP-complet et NP-difficile. Un problème NP-complet est à la fois dans NP et NP-difficile. Un problème seulement qualifié de NP-difficile n'est pas nécessairement un problème de décision vérifiable dans NP.

NP et « non polynomial ». Les lettres NP ne signifient pas qu'un problème exige forcément un temps non polynomial. Le critère testable est l'existence d'une vérification polynomiale des certificats positifs ; savoir si tous ces problèmes sont aussi résolubles en temps polynomial revient à la question P = NP.

Décision et optimisation. Demander si une tournée respecte une borne appelle oui ou non ; chercher la tournée la plus courte demande une valeur et une solution optimale. La source classe comme NP-complète la version décisionnelle du voyageur de commerce.

La vérification polynomiale porte sur un certificat associé à une instance positive. Elle ne signifie ni que toute chaîne proposée est une solution, ni qu'un certificat doit être fourni pour une instance négative. Il faut préciser le certificat et le vérificateur.

Une réduction ne doit pas déformer le verdict et doit être calculable en temps polynomial. Une simple ressemblance entre deux problèmes ne suffit pas. Pour établir la difficulté du problème cible, la transformation part du problème déjà connu et va vers la cible.

NP-complet ne signifie pas « impossible à résoudre » pour chaque instance. La classification concerne une famille d'instances et une borne asymptotique de pire cas. Il faut distinguer ce statut théorique du temps observé sur une taille ou une structure particulière.

L'absence actuelle d'algorithme polynomial connu ne constitue pas une preuve que P est différent de NP. Le cas charnière reste précisément ouvert : un seul algorithme polynomial pour un problème NP-complet suffirait à obtenir P = NP.

Le théorème de Cook fait de SAT le premier point d'appui historique de la NP-complétude. À partir d'un problème NP-complet connu, une nouvelle réduction polynomiale peut transférer la difficulté vers un autre problème de décision.

La question P = NP condense l'enjeu : la vérification polynomiale d'un certificat positif implique-t-elle toujours l'existence d'un algorithme polynomial qui détermine le verdict ? Une réponse positive rendrait tous les problèmes NP-complets résolubles en temps polynomial.