NP-complétude et algorithmes d'approximation

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• passer d'un problème d'optimisation à sa version décisionnelle et retour, et dire pourquoi la théorie se construit sur la seconde;
• mesurer la taille d'une instance par la longueur de son codage, et reconnaître un algorithme pseudo-polynomial — celui du sac à dos au chapitre 10 en est un;
• définir $P$ et définir $NP$ par les certificats et le vérificateur, exhiber un certificat pour chacun des problèmes du catalogue, et démontrer $P\subseteq NP$;
• écrire une réduction polynomiale $A{\le }_{p}B$, énoncer sans vous tromper de sens ce qu'elle permet de conclure, et l'appliquer pour transporter la $NP$-complétude;
• construire en entier la réduction de 3-SAT vers la couverture par sommets et en démontrer les deux sens;
• choisir une stratégie face à un problème $NP$-complet — exact avec élagage, complexité paramétrée, heuristique, approximation — et démontrer la garantie d'un algorithme 2-approché.

La question que dix chapitres ont laissée ouverte

Depuis le chapitre 1, la démarche de ce cours est invariable: on pose un problème, on conçoit un algorithme, on compte ses opérations et on range le compte dans une classe de croissance. Le tri par insertion était en $\Theta (n^2)$ comparaisons dans le pire des cas, le tri fusion en $\Theta (n\log n)$, et le chapitre 3 a même démontré que ce second résultat est optimal: aucun tri par comparaisons ne peut faire mieux que $\Omega (n\log n)$. Dijkstra, au chapitre 7, calcule les plus courts chemins en $O((n+m)\log n)$; Kruskal, au chapitre 8, un arbre couvrant minimal en . Chaque fois, la question «existe-t-il un algorithme efficace?» a reçu une réponse, et cette réponse était oui.

Le chapitre 10 a été le premier à hésiter. Le sac à dos 0/1 y est résolu par une table de programmation dynamique en $O(nW)$ opérations, où $W$ est la capacité. Sur l'instance du cours — capacité $W=9$, quatre objets, optimum 13 — la table se remplit en un clin d'œil. Sur une instance où les poids sont des entiers de quarante bits, la même table compte $nW$ cases, soit pour cent objets environ $1,1\times 10^{14}$ cases, alors que l'instance elle-même tient en quatre mille bits. Quelque chose ne va pas dans notre manière de compter, et ce chapitre commence par le dire.

Il y a plus dérangeant. Pour certains problèmes qui ressemblent beaucoup à ceux que nous avons résolus, personne n'a jamais trouvé d'algorithme polynomial. Trouver un arbre couvrant minimal est facile; trouver un cycle hamiltonien, c'est-à-dire un circuit qui passe une fois et une seule par chaque sommet, résiste depuis soixante ans. Trouver un plus court chemin est facile; trouver la plus courte tournée qui visite toutes les villes résiste tout autant. Décider si un graphe est connexe est facile; décider s'il possède une clique de taille donnée résiste.

Ce chapitre est la théorie de cette résistance. Elle ne dit pas — et c'est le point le plus important du chapitre — que ces problèmes sont insolubles. Elle dit quelque chose de plus subtil et de plus utile: ils sont tous le même problème. Un algorithme polynomial pour l'un en donnerait un pour tous les autres. Cette solidarité, découverte au début des années 1970, transforme une collection d'échecs individuels en une question unique, ouverte, et dotée depuis l'an 2000 d'une récompense d'un million de dollars.

Décider plutôt qu'optimiser

Trois formes d'un même problème

Prenons la couverture par sommets, qui sera le fil de tout le chapitre.

Ce problème se pose sous trois formes, et la distinction n'est pas un raffinement de logicien.

• Forme d'optimisation: étant donné $G$, calculer $\tau (G)$.
• Forme de recherche: étant donné $G$, produire une couverture de taille $\tau (G)$.
• Forme de décision: étant donnés $G$ et un entier $k$, répondre par oui ou non à la question «$G$ possède-t-il une couverture par sommets de taille au plus $k$?».

Toute la théorie qui suit se bâtit sur la troisième. La raison est technique et elle est solide: un problème de décision est un ensemble de mots — l'ensemble des codages d'instances dont la réponse est oui — et les ensembles se comparent, s'intersectent, se réduisent les uns aux autres. Une fonction qui rend un entier ou un sous-ensemble ne se prête pas à ce traitement. On perd en apparence de la généralité; la proposition suivante montre qu'on n'en perd aucune.

Démonstration. L'implication $3\Rightarrow 2$ est immédiate — on produit une couverture minimum et on compte ses éléments — et $2\Rightarrow 1$ l'est tout autant: on calcule $\tau (G)$ et on le compare à $k$. Reste $1\Rightarrow 3$, qui est la seule direction instructive.

Supposons donc disposer d'un sous-programme $\mathrm{DEC}(G,k)$ polynomial qui répond à la question de décision. Notons $n=|V|$.

Étape 1: trouver la valeur optimale. La fonction $k\mapsto \mathrm{DEC}(G,k)$ est croissante au sens où elle vaut non jusqu'à un certain seuil puis oui après: si une couverture de taille $k$ existe, toute sur-ensemble de taille $k+1$ en est encore une. On peut donc dichotomiser sur $k\in \{0,1,\dots ,n\}$ exactement comme au chapitre 2, et obtenir $\tau (G)$ en appels.

Étape 2: reconstruire une couverture. Posons $k=\tau (G)$ et $S=\varnothing$, et répétons tant qu'il reste une arête. Pour chaque sommet $v$ du graphe courant, notons $G-v$ le graphe obtenu en supprimant $v$ et toutes les arêtes qui le touchent, et demandons $\mathrm{DEC}(G-v,k-1)$.

Cette question est exactement «$G$ possède-t-il une couverture de taille $k$ contenant $v$?». En effet, si $S^{\prime }$ couvre $G$, contient $v$ et vérifie $|S^{\prime }|\le k$, alors couvre et compte au plus éléments; réciproquement, si couvre avec , alors couvre — toute arête supprimée touchait — et compte au plus éléments.

Comme $G$ possède une couverture de taille $k$ et que cette couverture est non vide dès qu'il reste une arête, au moins un sommet $v$ reçoit la réponse oui. On prend le premier, on l'ajoute à $S$, on remplace $G$ par $G-v$ et $k$ par $k-1$, et l'invariant «le graphe courant possède une couverture de taille $k$» est préservé. Le processus s'arrête quand il n'y a plus d'arête, et est alors une couverture de de taille au plus , donc exactement .

Coût. Chaque tour supprime un sommet, il y a donc au plus $n$ tours, et chaque tour fait au plus $n$ appels: au total $O(n^2)$ appels à $\mathrm{DEC}$, plus la dichotomie. Un nombre polynomial d'appels à un sous-programme polynomial, sur des instances qui ne grossissent pas, donne un algorithme polynomial. $\square$

Cette technique porte un nom, l'auto-réductibilité: on interroge le sous-programme de décision sur des instances plus petites du même problème pour reconstruire la solution. Retenez-la, car elle a une conséquence spectaculaire que nous énoncerons plus loin: si quelqu'un trouvait un jour un algorithme polynomial répondant simplement oui ou non à la question «cette formule est-elle satisfaisable?», on saurait immédiatement construire l'affectation satisfaisante en temps polynomial.

La taille d'une instance: le piège du codage

La taille est la longueur de l'écriture

Le chapitre 1 avait posé la règle et annoncé qu'on y reviendrait ici: la taille d'une instance est le nombre de bits qu'il faut pour l'écrire, pas la valeur des nombres qu'elle contient.

Cette convention est ce qui donne un sens à «temps polynomial». Un algorithme est polynomial si son coût est borné par un polynôme en $|x|$. Elle a une conséquence désagréable pour le chapitre 10.

La classe P

Deux remarques sur cette définition, toutes deux importantes.

D'abord, elle est robuste. Changer de modèle de calcul raisonnable — machine de Turing, machine RAM, langage de programmation quelconque — ne modifie le coût que d'un facteur polynomial, donc ne modifie pas $P$. Changer de codage raisonnable non plus. C'est cette robustesse qui fait de «polynomial» une notion mathématique et non une convention d'ingénieur, et c'est ce qu'on appelle parfois la thèse de Cobham–Edmonds: «calculable efficacement» signifie «calculable en temps polynomial».

Ensuite, elle est grossière, et volontairement. Un algorithme en $n^{100}$ est polynomial et parfaitement inutilisable; un algorithme en $2^{n/1000}$ est exponentiel et praticable jusqu'à des tailles considérables. La frontière polynomial / exponentiel n'est donc pas la frontière praticable / impraticable. Elle est choisie pour une autre raison: elle est stable — stable par composition, par itération polynomiale, par changement de modèle — et cette stabilité est ce qui permet de démontrer des théorèmes. Le fait empirique, constaté depuis soixante ans, est qu'un problème naturel qui tombe dans $P$ y tombe presque toujours avec un exposant petit, 1, 2 ou 3.

Tout ce cours, jusqu'ici, a peuplé $P$: la recherche dichotomique, les tris du chapitre 3, les parcours du chapitre 6, Dijkstra et Bellman–Ford au chapitre 7, Kruskal et Prim au chapitre 8, Huffman au chapitre 9, la sous-séquence commune et la distance d'édition au chapitre 10. Sous forme décisionnelle — «existe-t-il un arbre couvrant de poids au plus $k$?», «la distance d'édition est-elle inférieure ou égale à $k$?» — ce sont tous des problèmes de $P$.

La classe NP: vérifier plutôt que résoudre

Le certificat et le vérificateur

Voici l'idée centrale du chapitre, et elle est étonnamment simple. Pour beaucoup de problèmes difficiles, trouver une solution semble hors de portée, mais vérifier une solution qu'on vous tend est facile. Trouver un cycle hamiltonien dans un graphe à mille sommets, personne ne sait le faire vite; si on vous donne l'ordre des mille sommets, vérifier que c'est bien un cycle qui les visite tous une fois prend mille lectures d'adjacence.

C'est cette asymétrie que la classe $NP$ formalise. Nous la définissons par les certificats, et non par les machines non déterministes dont elle tire son nom — les deux définitions sont équivalentes, et celle-ci se manipule sans avoir à introduire un modèle de machine.

Lisez la double implication dans les deux sens, car les deux comptent et l'oubli du second est une erreur fréquente.

• Complétude (de gauche à droite): si la réponse est oui, il existe un certificat que le vérificateur accepte. Il existe — on ne dit pas comment le trouver, et c'est tout le sujet du chapitre.
• Correction (de droite à gauche): si la réponse est non, aucun certificat, aussi astucieux soit-il, n'est accepté. Un vérificateur laxiste, qui accepterait un mauvais certificat sur une instance négative, ne définit rien.

Remarquez enfin l'asymétrie de la définition: elle donne une preuve courte du oui, jamais du non. Rien, dans «ce graphe n'a pas de cycle hamiltonien», ne se certifie en temps polynomial de manière évidente — et savoir si c'est possible est une autre question ouverte, celle de l'égalité entre $NP$ et $co\text{-}NP$.

Démonstration. Soit $A\in P$, et soit $M$ un algorithme qui décide $A$ en temps $p(|x|)$. Construisons un vérificateur $V$ ainsi: sur l'entrée $(x,c)$, $V$ ignore $c$, exécute $M$ sur et renvoie la réponse de .

Vérifions les deux sens de la définition. Si $x$ est positive, alors $M(x)$ répond oui, donc $V(x,c)$ répond oui pour n'importe quel $c$, en particulier pour le mot vide, dont la longueur $0$ est bien bornée par tout polynôme. Si $x$ est négative, $M(x)$ répond non, donc $V(x,c)$ répond non pour tout $c$: aucun certificat n'est accepté. Enfin s'exécute en temps , qui est polynomial. Donc .

L'autre inclusion, $NP\subseteq P$, est la question ouverte. On sait en revanche borner $NP$ par le haut, et cette borne mérite d'être énoncée parce qu'elle rassure: aucun problème de $NP$ n'est insoluble.

Démonstration. Soit $V$ un vérificateur polynomial pour $A$ et $q$ le polynôme bornant la longueur des certificats. Sur une instance $x$ de taille $n$, énumérons tous les mots $c$ de longueur au plus $q(n)$ — il y en a $2^{q(n)+1}-1$ sur l'alphabet binaire — et exécutons sur chacun. Par la complétude, si est positive l'un de ces mots est accepté; par la correction, si est négative aucun ne l'est. L'algorithme répond donc correctement, et son coût est le produit du nombre de certificats par le coût de , soit .

On a donc la chaîne $P\subseteq NP\subseteq EXPTIME$, où $EXPTIME$ est la classe des problèmes résolubles en temps $2^{\mathrm{poly}(n)}$. Et l'on sait, par le théorème de hiérarchie en temps, que $P⊊EXPTIME$: il existe des problèmes résolubles en temps exponentiel et démontrablement pas en temps polynomial. Il en résulte un fait souvent ignoré: On ne sait pas laquelle.

Deux mots sur la région intermédiaire, parce qu'elle est régulièrement mal citée. Le théorème de Ladner (1975) affirme que si $P\ne NP$, alors il existe dans $NP$ des problèmes qui ne sont ni dans $P$ ni $NP$-complets. Il ne dit pas lesquels: il les construit artificiellement par diagonalisation. Les deux candidats naturels ont chacun un argument sérieux et aucune preuve. La factorisation (sous forme décisionnelle: «$N$ a-t-il un facteur non trivial inférieur à $k$?») appartient à $NP$ et aussi à — un certificat de non-existence est la décomposition complète de en facteurs premiers, accompagnée d'un certificat de primalité pour chacun —, or si un problème -complet était dans , on aurait , ce que personne ne croit. L', lui, dispose depuis 2015 d'un algorithme en temps quasi-polynomial dû à László Babai, ce qui rend sa -complétude très improbable sans la réfuter.

L'explorateur ci-dessus tient en une phrase tout ce que la section vient de dire. La formule a cinq variables et neuf clauses, et une seule des $2^5=32$ affectations la satisfait — c'est l'affectation numéro 14, $x_1=F$, $x_2=V$, , , . Balayez le premier curseur: vous rencontrerez vingt-six affectations qui satisfont clauses sur neuf, et qui ne valent rien, parce qu'une clause vide suffit à tout invalider. Pendant ce temps, le dernier affichage ne bouge jamais: vérifier une affectation coûte toujours vingt-sept lectures de littéral. C'est cette invariance qui définit , et c'est l'autre curseur qui dit le prix de la recherche: à cinquante variables, il faudrait essayer affectations pour la même vérification à vingt-sept lectures.

Réductions polynomiales

Traduire un problème en un autre

Deux précisions sur la définition. La condition 2 est une équivalence, pas une implication: une «réduction» qui ne démontrerait qu'un sens ne réduit rien, et c'est l'erreur que la section suivante s'emploiera à ne pas commettre. La condition 1 entraîne au passage que $|f(x)|$ est polynomial en $|x|$, puisqu'un algorithme qui tourne en temps $p(|x|)$ ne peut pas écrire plus de $p(|x|)$ symboles.

Démonstration. Soit $f$ la réduction, calculable en temps $p(|x|)$ pour un polynôme $p$.

1. Supposons $B\in P$, décidé par un algorithme $M_B$ de coût $q$. Voici un algorithme pour $A$: sur l'entrée $x$, calculer $y=f(x)$, puis exécuter $M_B(y)$ et renvoyer sa réponse. Il est correct par la condition 2, dans les deux sens: si est positive alors l'est, donc répond oui; si est négative alors l'est aussi, donc répond non. Son coût est , et comme , ce coût est majoré par . La composée de deux polynômes est un polynôme, donc .

2. Même construction avec le vérificateur: si $V_B$ vérifie $B$ en temps polynomial, alors $V_A(x,c)=V_B(f(x),c)$ vérifie en temps polynomial. La complétude et la correction se transportent par l'équivalence de la condition 2.

3. C'est la contraposée du point 1: si $B$ était dans $P$, $A$ y serait, contrairement à l'hypothèse.

Transitivité. Si $f$ réduit $A$ à $B$ en temps $p$ et $g$ réduit $B$ à $C$ en temps $r$, alors $g\circ f$ réduit $A$ à : l'équivalence se compose, et le coût est polynomial.

Le sens, et rien que le sens

NP-difficile, NP-complet, et le théorème de Cook–Levin

La définition a une conséquence immédiate, et c'est elle qui donne toute sa force à la notion.

Démonstration. Supposons $B\in P$ et soit $A\in NP$ quelconque. Comme $B$ est $NP$-difficile, on a $A{\le }_{p}B$; par le point 1 du théorème 11.4, $A\in P$. Ceci valant pour tout , on obtient , et l'inclusion inverse est le théorème 11.2: donc . La seconde affirmation est la contraposée de la première.

Reste à savoir si de tels problèmes existent. Rien, dans la définition, ne le garantit: elle exige une réduction depuis tous les problèmes de $NP$, c'est-à-dire depuis une infinité de problèmes dont on ne sait rien d'autre que l'existence d'un vérificateur. C'est ce verrou que le théorème suivant a fait sauter.

Nous admettons ce théorème, démontré indépendamment par Stephen Cook en 1971 et Leonid Levin en 1973, et voici précisément pourquoi. Sa démonstration prend un problème $A\in NP$ quelconque, avec son vérificateur polynomial $V$, et construit une formule booléenne dont les affectations satisfaisantes sont exactement les exécutions acceptantes de $V$ sur l'instance donnée. Pour cela il faut disposer d'un modèle de calcul formel — une machine de Turing, avec ses états, son ruban et sa fonction de transition — et coder, par des variables booléennes, le contenu de chaque case du ruban à chaque instant, puis exprimer par des clauses le fait que chaque configuration succède légalement à la précédente. La machine RAM du chapitre 1 ne se prête pas à cet encodage, et introduire la machine de Turing prendrait un chapitre entier: ce travail appartient à un cours de théorie de la complexité, pas à un cours d'algorithmique. Ce que nous retenons ici, c'est l'énoncé, qui se manipule parfaitement sans sa démonstration.

Une fois SAT tenu pour $NP$-complet, tout le reste s'obtient par réductions, grâce au lemme de transport suivant.

Démonstration. Soit $C\in NP$ quelconque. Comme $A$ est $NP$-difficile, $C{\le }_{p}A$; par hypothèse $A{\le }_{p}B$; par transitivité de (théorème 11.4), . Ceci valant pour tout , est -difficile. La seconde affirmation est alors la définition de la -complétude.

C'est exactement ce programme que Richard Karp a exécuté en 1972, en établissant la $NP$-complétude de vingt et un problèmes classiques à partir de SAT — dont la couverture par sommets, la clique, l'ensemble indépendant, le cycle hamiltonien, la partition et le sac à dos. Depuis, le catalogue s'est étendu à des milliers de problèmes, dans tous les domaines: ordonnancement, découpe, placement, repliement de protéines, vérification de circuits.

Une réduction en entier: de 3-SAT à la couverture par sommets

Nous allons maintenant faire, en détail et sans rien admettre, ce que la section précédente a décrit en général. L'objectif est double: obtenir le résultat, et surtout voir à quoi ressemble la démonstration des deux sens, puisque c'est là que se juge une réduction.

La construction

Soit $\phi$ une formule 3-SAT à $n$ variables $x_1,\dots ,x_n$ et $m$ clauses $c_1,\dots ,c_m$, chaque clause étant une disjonction de trois littéraux portant sur trois variables distinctes. On construit un graphe et un entier ainsi.

Les modules de variable. Pour chaque variable $x_i$, deux sommets étiquetés $x_i$ et $\neg x_i$, reliés par une arête. Cela fait $2n$ sommets et $n$ arêtes.

Les modules de clause. Pour chaque clause $c_j=({\ell }_{j,1}\vee {\ell }_{j,2}\vee {\ell }_{j,3})$, trois sommets formant un . Cela fait sommets et arêtes.

Les arêtes de liaison. Pour chaque clause $c_j$ et chaque position $t\in \{1,2,3\}$, une arête entre le sommet de triangle $c_j^t$ et le sommet de littéral correspondant à ${\ell }_{j,t}$. Cela fait arêtes.

Le seuil. On pose $k=n+2m$.

Au total, $G_{\phi }$ possède $2n+3m$ sommets et $n+6m$ arêtes, et la construction se fait en parcourant une fois la formule: elle est clairement calculable en temps linéaire en la taille de $\phi$, donc polynomial.

La démonstration, dans les deux sens

Commençons par le lemme de comptage, qui sert aux deux sens et qui explique le choix du seuil.

Démonstration. Les $n$ arêtes de variable et les $m$ triangles forment $n+m$ sous-graphes deux à deux disjoints: aucun sommet n'appartient à deux d'entre eux, puisqu'un sommet de littéral n'est dans aucun triangle et réciproquement.

Soit $S$ une couverture. Pour chaque $i$, l'arête $\{x_i,\neg x_i\}$ doit être couverte, donc $S$ contient au moins un de ses deux sommets. Pour chaque $j$, le triangle $c_j^1{c}_j^2{c}_j^3$ a trois arêtes; si n'en contenait qu'un sommet au plus, l'arête joignant les deux autres ne serait pas couverte. Donc contient au moins deux sommets de chaque triangle.

Ces contributions portent sur des ensembles disjoints de sommets, donc elles s'additionnent:

Si $|S|=n+2m$, aucune des minorations ne peut être stricte et $S$ ne peut contenir aucun sommet supplémentaire: il y a exactement un sommet par module de variable, exactement deux par triangle, et rien d'autre. $\square$

Démonstration. Nous démontrons séparément les deux implications; aucune ne découle de l'autre.

Sens direct: satisfaisable $\Rightarrow$ couverture de taille $k$. Soit $\alpha$ une affectation satisfaisant $\phi$. Construisons $S$ ainsi.

Pour chaque variable $x_i$, mettons dans $S$ le sommet du littéral vrai sous $\alpha$: le sommet $x_i$ si $\alpha (x_i)$ est vrai, le sommet sinon. Cela fait sommets.

Pour chaque clause $c_j$: comme $\alpha$ satisfait $\phi$, elle satisfait $c_j$, donc au moins un littéral ${\ell }_{j,t_j}$ de est vrai sous ; choisissons-en un et mettons dans les sommets du triangle, pour . Cela fait sommets, et au total .

Vérifions que $S$ couvre les trois familles d'arêtes.

• Les $n$ arêtes de variable: chacune a exactement un de ses deux sommets dans $S$, par construction. Couverte.
• Les $3m$ arêtes de triangle: dans chaque triangle, un seul sommet est hors de $S$, donc toute arête du triangle a au moins une extrémité dans $S$. Couverte.
• Les $3m$ arêtes de liaison: soit $\{c_j^t,\ell \}$ une telle arête. Si , le sommet est dans et l'arête est couverte. Si , le sommet de triangle est hors de , mais alors est sous , donc le sommet de littéral a été mis dans à la première étape. Couverte.

Donc $S$ est une couverture de taille $k$.

Sens réciproque: couverture de taille au plus $k$ $\Rightarrow$ satisfaisable. Soit $S$ une couverture avec $|S|\le k=n+2m$. Le théorème 11.8 donne $|S|\ge n+2m$, donc $|S|=n+2m$ exactement, et contient exactement un sommet de chaque module de variable et exactement deux sommets de chaque triangle.

Définissons l'affectation $\alpha$ par: $\alpha (x_i)$ est vrai si le sommet $x_i$ appartient à $S$, faux si c'est le sommet $\neg x_i$ qui y appartient. Cette définition est licite et non ambiguë précisément parce que contient exactement un des deux.

Montrons que $\alpha$ satisfait chaque clause $c_j$. Dans le triangle de $c_j$, exactement un sommet est hors de $S$; notons-le $c_j^{t_0}$ et soit le littéral qu'il représente. L'arête de liaison appartient à et doit être couverte par ; comme , c'est . Par définition de , le littéral est donc vrai sous . Or est l'un des trois littéraux de : la clause est satisfaite.

Ceci vaut pour toute clause, donc $\alpha$ satisfait $\phi$.

Conclusion. La transformation $\phi \mapsto (G_{\phi },k)$ se calcule en temps polynomial et l'équivalence est établie dans les deux sens: c'est une réduction, donc 3-SAT ${\le }_p$ couverture par sommets. Comme 3-SAT est $NP$-difficile (théorème 11.6) et que la couverture par sommets est dans $NP$ (exemple 11.2), le théorème 11.7 conclut: la couverture par sommets est $NP$-complète.

Que faire quand votre problème est NP-complet

Vous avez démontré, ou trouvé dans le catalogue, que le problème posé par votre application est $NP$-complet. Cette conclusion n'est pas la fin du travail: c'est le moment où l'on cesse de chercher l'algorithme polynomial exact — et c'est déjà beaucoup, parce qu'on ne le cherche plus en vain — pour choisir l'un des quatre chemins qui restent.

Exact, mais exponentiel avec élagage

Le premier chemin garde l'exactitude et paie le prix. La force brute est rarement la bonne façon de le faire: on lui préfère une exploration arborescente qui élague, c'est-à-dire qui abandonne une branche dès qu'elle ne peut plus contenir de solution meilleure que la meilleure déjà connue. C'est la séparation et évaluation (branch and bound), et sa qualité tient entièrement à celle de la borne utilisée pour élaguer.

La programmation dynamique du chapitre 10 offre parfois un gain spectaculaire sur la force brute pure sans sortir de l'exponentiel. Pour le voyageur de commerce, l'énumération des tournées coûte $(n-1)!/2$, soit $6,1\times 10^{16}$ pour vingt villes; l'algorithme de Held et Karp, qui tabule le meilleur chemin pour chaque paire (sous-ensemble visité, ville courante), coûte $\Theta (n^2{2}^n)$, soit environ $4,2\times 10^8$ pour les mêmes vingt villes. Huit ordres de grandeur gagnés — et l'algorithme reste exponentiel, donc impraticable vers quarante villes.

Complexité paramétrée: isoler ce qui est petit

Le deuxième chemin consiste à remarquer que la difficulté ne dépend pas seulement de $n$, mais souvent d'un paramètre qui, dans votre application, reste petit. On cherche alors un algorithme en $f(k)\cdot \mathrm{poly}(n)$, où toute l'explosion est confinée dans $f(k)$: on dit que le problème est FPT pour ce paramètre.

Démonstration. L'algorithme est une recherche arborescente bornée. Sur l'entrée $(G,k)$: s'il n'y a plus d'arête, répondre oui — l'ensemble vide convient. Si $k=0$ et qu'il reste une arête, répondre non. Sinon, choisir une arête quelconque $\{u,v\}$ et répondre oui si l'un au moins des deux appels récursifs $(G-u,k-1)$ ou $(G-v,k-1)$ répond oui.

Correction. Toute couverture de $G$ doit contenir $u$ ou $v$, puisque l'arête $\{u,v\}$ doit être couverte. Si elle contient $u$, alors en lui retirant $u$ on obtient une couverture de $G-u$ de taille au plus $k-1$, et réciproquement, ajouter $u$ à une couverture de de taille couvre , puisque toute arête supprimée touchait . Le même raisonnement vaut pour . L'algorithme explore donc exactement les deux cas possibles, et les cas de base sont corrects.

Coût. L'arbre des appels est binaire et de profondeur au plus $k$, puisque $k$ décroît d'une unité à chaque descente: il compte donc au plus $2^{k+1}-1$ nœuds. Chaque nœud effectue le choix d'une arête et la suppression d'un sommet, en $O(n+m)$. D'où le coût annoncé. $\square$

Lisez ce résultat avec le tableau du chapitre 1. Pour $n=1000$ sommets, $m=2000$ arêtes et $k=20$, le coût vaut environ $2^{20}\times 3000\approx 3,1\times 10^9$ opérations: c'est au bord du praticable, sur un graphe où la force brute aurait demandé sous-ensembles, un nombre à quarante et un chiffres. Le paramètre a tout changé — et il ne change rien du tout si vaut 200.

Heuristiques: renoncer à la garantie

Le troisième chemin renonce à toute garantie et mise sur le fait que vos instances ne sont pas les pires. C'est le domaine des solveurs SAT modernes, de la recherche locale, du recuit simulé, des métaheuristiques. Ces méthodes n'offrent aucune borne sur la qualité de ce qu'elles rendent ni sur le temps qu'elles mettent, et elles fonctionnent remarquablement bien sur d'immenses classes d'instances réelles.

Il faut les juger pour ce qu'elles sont. Une heuristique qui donne de bons résultats sur trois cents instances de votre banc d'essai est un outil légitime et documenté; ce n'est pas un théorème, et le chapitre 9 avait déjà posé la règle à propos des algorithmes gloutons: un algorithme qui marche sur trois exemples n'est pas démontré. La différence entre une heuristique et la section suivante tient en un mot: la garantie.

Approximation: renoncer à l'optimum, garder une garantie

Le quatrième chemin est le plus satisfaisant intellectuellement. On renonce à l'optimum, mais on démontre de combien on peut s'en écarter — dans le pire des cas, sur toutes les instances.

Insistons sur le mot toute. Un algorithme 2-approché ne promet pas d'être deux fois moins bon en moyenne: il promet de ne jamais dépasser le double de l'optimum, sur aucune instance, y compris celle qu'un adversaire aurait construite contre lui. C'est un énoncé de pire cas, de la même famille que les garanties du chapitre 1, et c'est ce qui en fait un théorème plutôt qu'une observation.

Remarquez aussi le tour de force logique: la démonstration doit comparer ce que l'algorithme rend à un optimum qu'elle ne sait pas calculer. Elle y parvient en minorant l'optimum par une quantité que l'algorithme, lui, connaît. Voyons ce mécanisme sur l'exemple canonique.

Le 2-approché de la couverture par sommets

L'algorithme tient en six lignes et il est d'une naïveté déconcertante.

def couverture_par_couplage(aretes):
    """Rend une couverture par sommets dont la taille est au plus deux fois l'optimum."""
    pris = set()
    couplage = []
    for u, v in aretes:
        if u not in pris and v not in pris:
            couplage.append((u, v))          # arete ajoutee au couplage
            pris.add(u)
            pris.add(v)                      # ses DEUX extremites entrent dans la couverture
    return couplage, sorted(pris)

Le coût est immédiat: une passe sur les $m$ arêtes, chacune avec deux tests d'appartenance en $O(1)$ amorti (chapitre 4), donc $\Theta (m)$ opérations. L'algorithme construit un couplage maximal — un ensemble d'arêtes deux à deux disjointes auquel on ne peut plus rien ajouter — et rend les deux extrémités de chacune de ses arêtes.

La première réaction est en général l'incrédulité: prendre les deux extrémités semble un gaspillage évident, puisqu'une seule suffirait à couvrir l'arête. C'est vrai, et c'est précisément ce qui rend la garantie démontrable.

Démonstration. 1. $S$ est une couverture. Raisonnons par l'absurde et supposons qu'une arête $\{u,v\}\in E$ ne soit couverte par aucun sommet de $S$: ni $u$ ni $v$ n'appartient à $S$. Comme $S$ est exactement l'ensemble des extrémités des arêtes de $M$, cela signifie que ni $u$ ni n'est l'extrémité d'une arête de . L'arête est donc disjointe de toutes les arêtes de , et est encore un couplage — ce qui contredit la de . Donc toute arête est couverte.

2. $|M|\le \tau (G)$. Soit $S^{\star }$ une couverture minimum, de taille $\tau (G)$. Chaque arête de $M$ doit être couverte, donc $S^{\star }$ contient au moins une de ses deux extrémités; choisissons-en une et notons $\sigma (e)\in S^{\star }$ ce sommet, pour chaque . L'application ainsi définie est : si deux arêtes distinctes de donnaient le même sommet , ce sommet appartiendrait aux deux arêtes, qui ne seraient donc pas disjointes — or les arêtes d'un couplage le sont. Une injection de dans donne .

3. Les arêtes de $M$ étant deux à deux disjointes, elles apportent $2|M|$ sommets distincts, donc $|S|=2|M|$. En combinant avec le point 2:

Comme $S$ est une couverture (point 1) et que l'algorithme s'exécute en $\Theta (m)$, il est bien 2-approché. $\square$

Reprenez le raisonnement et voyez où passe l'astuce. L'algorithme ne connaît pas $\tau (G)$ — le calculer est précisément le problème $NP$-difficile qu'on renonce à résoudre. Mais il connaît $|M|$, et le point 2 établit que ce nombre est une minoration de $\tau (G)$. On compare donc le résultat, $2|M|$, à une quantité connue, $|M|$, elle-même sous l'optimum. C'est le schéma de presque toutes les démonstrations d'approximation: trouver une minoration calculable de l'optimum, et borner le résultat par un multiple de cette minoration.

Un dividende du chapitre 8: le voyageur de commerce métrique

Le plus joli exemple d'approximation de ce chapitre ne demande aucun outil nouveau: il utilise l'arbre couvrant minimal du chapitre 8.

Démonstration. Trois étapes, dont la première est la minoration calculable dont nous avons parlé.

1. $w(T)\le \mathrm{OPT}$. Soit ${\mathcal{T}}^{\star }$ une tournée optimale, de coût $\mathrm{OPT}$. Retirons-lui une arête quelconque: il reste un chemin qui passe par toutes les villes, donc un arbre couvrant, dont le poids vaut $\mathrm{OPT}$ moins celui de l'arête retirée, donc au plus $\mathrm{OPT}$ puisque les distances sont positives. Comme $T$ est un arbre couvrant minimal, $w(T)$ est inférieur ou égal au poids de cet arbre-là, donc .

2. La marche qui double l'arbre coûte $2w(T)$. Parcourons $T$ en profondeur depuis une racine quelconque et écrivons la suite des sommets rencontrés, en notant chaque sommet à l'aller et au retour. Cette marche fermée emprunte chaque arête de $T$ exactement deux fois — une fois dans chaque sens — et visite tous les sommets; son coût vaut donc exactement $2w(T)$.

3. Les raccourcis ne coûtent rien. La marche repasse par des sommets déjà vus. Supprimons de la suite toutes les occurrences répétées, ne gardant que la première: on obtient exactement l'ordre préfixe, c'est-à-dire la tournée $\mathcal{T}$. Chaque suppression remplace un trajet $u\to z\to v$ par le trajet direct $u\to v$, et l'inégalité triangulaire donne $w(u,v)\le w(u,z)+w(z,v)$: Par récurrence sur le nombre de suppressions, .

En combinant avec l'étape 1, $w(\mathcal{T})\le 2w(T)\le 2\mathrm{OPT}$. Le calcul de $T$ par Kruskal coûte $O(m\log m)$ et le parcours préfixe $O(n)$: l'ensemble est polynomial. $\square$

Le voyageur métrique a mieux que 2: l'algorithme de Christofides (1976) atteint le rapport $3/2$ en remplaçant le doublement de l'arbre par l'ajout d'un couplage parfait de poids minimum sur les sommets de degré impair. Ce $3/2$ a tenu quarante-quatre ans avant d'être battu, en 2020, d'une quantité infime mais non nulle — le genre de résultat qui dit surtout à quel point la question est dure.

Ce que l'approximation ne peut pas faire

Le tableau ne serait pas honnête s'il s'arrêtait aux bonnes nouvelles. Trois remarques, dans l'ordre croissant de sévérité.

Certains problèmes s'approchent aussi bien qu'on veut. Le sac à dos du chapitre 10 admet un schéma d'approximation entièrement polynomial: pour tout $\epsilon >0$, un algorithme polynomial en $n$ et en $1/\epsilon$ rend une sélection de valeur au moins $(1-\epsilon )\mathrm{OPT}$. On l'obtient en arrondissant les valeurs des objets à un multiple commun, puis en appliquant la table du chapitre 10 sur les valeurs arrondies — dont l'étendue est désormais bornée par un polynôme en $n/\epsilon$. Le sac à dos est donc $NP$-complet et approchable à volonté: les deux ne sont pas contradictoires.

Certains problèmes ont une limite d'approximation démontrée. Pour la couverture par sommets, on sait qu'aucun algorithme polynomial ne peut garantir un rapport meilleur qu'environ $1,36$ à moins que $P=NP$ (Dinur et Safra, 2005). L'écart entre ce 1,36 et le 2 de notre algorithme est encore ouvert. Ces résultats dits d'inapproximabilité reposent sur la théorie des preuves vérifiables probabilistiquement, développée au début des années 1990; leur démonstration est hors de portée de ce cours, mais leur forme est celle du théorème 11.5: si l'on savait approcher mieux, on saurait décider exactement, donc $P=NP$.

Certains problèmes ne s'approchent pas du tout. C'est le cas du voyageur de commerce général, c'est-à-dire sans inégalité triangulaire, et la démonstration est assez courte pour être donnée.

Démonstration. Supposons disposer d'un tel algorithme $\mathcal{A}$, et soit $G=(V,E)$ un graphe à $n$ sommets dont on veut décider s'il possède un cycle hamiltonien — problème $NP$-complet (Karp, 1972).

Construisons une instance du voyageur sur les mêmes $n$ villes, en posant

Cette construction est polynomiale: il y a $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ distances à écrire, chacune sur $O(\log (\rho n))$ bits.

Si $G$ possède un cycle hamiltonien, ce cycle est une tournée de coût exactement $n$, donc $\mathrm{OPT}\le n$, et l'algorithme rend une tournée de coût au plus $\rho n$.

Si $G$ n'en possède pas, toute tournée emprunte au moins une arête absente de $G$, donc au moins une distance $\rho n+1$; les $n-1$ autres coûtant au moins 1 chacune, toute tournée coûte au moins $(\rho n+1)+(n-1)=\rho n+n>\rho n$. L'algorithme, qui rend une tournée, rend donc plus que .

Il suffit alors de comparer le coût rendu par $\mathcal{A}$ au seuil $\rho n$: inférieur ou égal, il y a un cycle hamiltonien; strictement supérieur, il n'y en a pas. On aurait ainsi un algorithme polynomial pour un problème $NP$-complet, d'où $P=NP$ par le théorème 11.5. $\square$

Comparez les théorèmes 11.12 et 11.13: le même problème, à l'inégalité triangulaire près, passe d'«approchable à un facteur 2» à «inapprochable à tout facteur constant, sauf si $P=NP$». L'hypothèse métrique n'est pas un détail de confort, c'est elle qui porte tout le résultat. Voilà pourquoi ce cours n'énonce jamais un théorème d'approximation sans ses hypothèses.

Ce que «P différent de NP» est, et ce qu'on n'en sait pas

Il reste à dire, aussi précisément que possible, où en est la question — et à distinguer ce qui est démontré de ce qui est cru.

Ce qui est démontré. $P\subseteq NP$ (théorème 11.2). $NP\subseteq EXPTIME$ (théorème 11.3). $P⊊EXPTIME$, par le théorème de hiérarchie en temps, donc au moins l'une des deux premières inclusions est stricte. SAT est $NP$-complet (Cook–Levin), et des milliers de problèmes le sont avec lui, si bien qu'un algorithme polynomial pour l'un d'eux les résoudrait tous.

Ce qui est ouvert. L'égalité $P=NP$, posée sous cette forme au début des années 1970. Elle figure depuis 2000 parmi les sept problèmes du prix du millénaire de l'institut Clay, dotés chacun d'un million de dollars. Un demi-siècle d'efforts n'a produit ni démonstration ni réfutation.

Ce qui est cru, et qui n'est pas un argument. La grande majorité des spécialistes pense que $P\ne NP$. Les raisons invoquées sont sérieuses — des milliers de problèmes $NP$-complets attaqués par des milliers de chercheurs pendant cinquante ans sans qu'aucun algorithme polynomial n'émerge — mais ce sont des raisons de croire, pas des démonstrations. L'histoire des mathématiques est remplie de convictions unanimes que quelqu'un a fini par renverser.

Pourquoi c'est si difficile: trois barrières. Ce qui distingue cette question d'un problème seulement non résolu, c'est qu'on a démontré l'insuffisance de familles entières de techniques. La relativisation (Baker, Gill et Solovay, 1975) montre qu'il existe des oracles $A$ et $B$ pour lesquels $P^A=N{P}^A$ et $P^B\ne N{P}^B$: aucune démonstration qui resterait valable en présence d'un oracle quelconque — ce qui est le cas de la diagonalisation classique — ne peut donc trancher. Les (Razborov et Rudich, 1994) montrent que la méthode combinatoire qui avait permis de minorer la taille de certains circuits ne peut pas s'étendre, sauf à contredire l'existence de fonctions à sens unique. L' (Aaronson et Wigderson, 2008) étend la première barrière aux techniques algébriques qui avaient permis de contourner la relativisation. Trois fois, la communauté a démontré que ses propres outils ne suffiraient pas.

Ce que $P\ne NP$ ne dirait pas. Cinq choses, et il faut les connaître pour ne pas raconter n'importe quoi.

1. Il ne dirait rien de votre instance. C'est un énoncé de pire cas sur une famille infinie; votre graphe peut être facile et vos formules SAT résolues en une seconde par un solveur industriel.
2. Il n'interdirait pas les algorithmes sous-exponentiels. Rien dans $P\ne NP$ n'exclut un algorithme en $2^{O(\sqrt{n})}$ ou en , et de tels algorithmes existent pour des cas particuliers structurés. Les hypothèses qui les excluraient — ETH, SETH — sont des , strictement plus fortes que , et elles sont énoncées comme telles dans la littérature.

Ce que $P=NP$ ne donnerait pas non plus. Une démonstration pourrait être non constructive, ou produire un algorithme en $n^{100}$ avec une constante astronomique: la révolution pratique qu'on imagine parfois n'est pas garantie par l'égalité elle-même. Elle serait en revanche un séisme conceptuel: par l'auto-réductibilité du théorème 11.1, elle ferait de la recherche d'une preuve mathématique courte une tâche mécanique, ce qui est à peu près la raison pour laquelle presque personne n'y croit.

Terminons par où nous avons commencé. Face à un problème nouveau, vous disposez maintenant de trois réponses possibles, et de trois seulement: j'ai un algorithme polynomial, le voici; j'ai démontré que ce problème est $NP$-difficile, voici la réduction, et je passe aux approximations; ou je ne sais pas encore. La troisième est une réponse honnête et fréquente. Ce qui ne l'est pas, c'est la quatrième, celle qu'on entend trop souvent: c'est impossible. Personne, à ce jour, n'a le droit de la prononcer.

Synthèse

• La théorie se construit sur les problèmes de décision, sans perte de généralité: décision, optimisation et recherche sont polynomialement équivalentes (théorème 11.1), par dichotomie sur le seuil puis auto-réduction en $O(n^2)$ appels. La taille d'une instance est la longueur de son codage en bits, ce qui rend le $O(nW)$ du sac à dos pseudo-polynomial: pour cent objets et des poids de 40 bits, la table compte $1,1\times 10^{14}$ cases alors que l'instance tient en 4000 bits.
• $P$ est la classe des problèmes résolubles en temps polynomial; $NP$ celle des problèmes en temps polynomial, définie par un de taille polynomiale et un vérificateur, avec ses deux obligations — un certificat existe sur toute instance positive, aucun n'est accepté sur une instance négative. , et : au moins l'une des deux inclusions est stricte, on ne sait pas laquelle.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 34 pour $P$, $NP$, la $NP$-complétude et les réductions, chapitre 35 pour les algorithmes d'approximation, dont la couverture par sommets et le voyageur métrique.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, utile pour fixer le vocabulaire: «couverture par sommets», «réduction», «vérificateur», «problème $NP$-complet».
• Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 8, la meilleure présentation pédagogique des réductions, avec la distinction décision/optimisation traitée explicitement; chapitres 10 et 11 pour la complexité paramétrée et l'approximation.
• Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitre 8, court et remarquablement clair sur le catalogue des problèmes $NP$-complets et le graphe des réductions entre eux.
• Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman — la référence historique et le catalogue de plusieurs centaines de problèmes; c'est de là que vient la réduction de 3-SAT vers la couverture par sommets présentée ici.
• Arora & Barak, Computational Complexity: A Modern Approach, Cambridge University Press — pour la démonstration du théorème de Cook–Levin, admise dans ce chapitre, et pour les barrières de relativisation, de preuves naturelles et d'algébrisation.