Problèmes difficiles & approximation (NP)

Jusqu'ici, ce livre vous a appris à concevoir des algorithmes rapides. Ce chapitre fait l'inverse : il vous donne les outils pour prouver qu'aucun algorithme rapide n'existe pour un problème donné. Le lecteur pragmatique se cabre sans doute à l'idée d'investir du temps à démontrer qu'une chose est impossible. Pourquoi vaut-il mieux savoir que l'on ne sait pas faire quelque chose qui, de fait, ne peut être fait ?

La réponse de Skiena est limpide : la théorie de la NP-complétude est un outil immensément utile, même si elle ne fournit que des résultats négatifs. Elle permet de concentrer ses efforts là où ils comptent, en révélant qu'une certaine quête — un algorithme à la fois exact et rapide — est vouée à l'échec. Elle apprend aussi à reconnaître ce qui rend un problème difficile, ce qui ouvre la voie à le remodeler ou à l'attaquer autrement. Développer le flair pour savoir quels problèmes sont durs est une compétence essentielle du concepteur d'algorithmes, et elle ne s'acquiert qu'en pratiquant. L'idée centrale est celle de réduction (reduction) entre problèmes.

Les réductions : transférer la difficulté

Une réduction est une opération qui transforme un problème en un autre. Imaginez deux problèmes algorithmiques, baptisés Bandersnatch et Bo-billy. Supposons que je sache résoudre Bandersnatch de la façon suivante : je traduis l'entrée G en une instance Y de Bo-billy, j'appelle un sous-programme qui résout Bo-billy sur Y, et je renvoie sa réponse comme réponse à Bandersnatch.

Bandersnatch(G)
    Traduire l'entrée G en une instance Y du problème Bo-billy.
    Appeler le sous-programme Bo-billy sur Y.
    Renvoyer la réponse de Bo-billy(Y).

Ce schéma est correct à condition que la traduction préserve la réponse : pour toute instance G, on doit avoir Bandersnatch(G) = Bo-billy(Y). Si la traduction prend un temps O(P(n)), il y a deux conséquences, exactement symétriques :

• Si Bo-billy est facile, Bandersnatch l'est aussi. Un algorithme en O(P'(n)) pour Bo-billy me donne un algorithme en O(P(n) + P'(n)) pour Bandersnatch.
• Si Bandersnatch est dur, Bo-billy l'est aussi. Une borne inférieure sur Bandersnatch impose une borne inférieure sur Bo-billy, sans quoi la réduction permettrait de la violer.

Une allégorie de cour de récréation

Skiena résume tout par une fable. Des enfants se battent pour prouver qui est « costaud ». Adam bat Bill, qui bat Chuck. Qui, parmi eux, est réellement costaud ? Impossible de le dire sans étalon externe. Si l'on m'apprend que Chuck est en réalité Chuck Norris, certifié costaud, alors Adam et Bill le sont au moins autant. À l'inverse, si je vous dis que c'est une cour de maternelle et que même moi je peux battre Adam, alors aucun des trois n'est costaud. Chaque combat est une réduction. La satisfiabilité joue le rôle de Chuck Norris : le problème dont la difficulté est certifiée.

Problèmes de décision

Pour traduire commodément entre problèmes, on les ramène à leur forme la plus simple : les problèmes de décision (decision problems), dont la réponse se limite à vrai ou faux. La plupart des problèmes d'optimisation se reformulent ainsi sans perdre leur substance. Au lieu de demander la tournée la moins coûteuse du voyageur de commerce (traveling salesman, TSP), on demande : « existe-t-il une tournée de coût ≤ k ? » Une recherche dichotomique sur k permet ensuite de retrouver l'optimum. À partir d'ici, on raisonnera sur des problèmes de décision.

Réductions « heureuses » : réutiliser le connu

Avant de prouver des difficultés, observons que les réductions servent aussi à fabriquer de nouveaux algorithmes à partir d'anciens. C'est l'art d'un ingénieur paresseux : ramener une tâche à un problème déjà résolu. Voici trois exemples du livre.

Paire la plus proche. Trouver les deux nombres d'un ensemble dont l'écart est minimal se réduit au tri : après tri, la paire la plus proche est forcément formée de voisins.

// Réduction au tri : O(n log n).
function paireProchaineAssezProche(s: number[], t: number): boolean {
  const trie = [...s].sort((a, b) => a - b); // O(n log n)
  for (let i = 0; i + 1 < trie.length; i++) {
    if (trie[i + 1] - trie[i] <= t) return true; // O(n)
  }
  return false;
}

Plus petit commun multiple. On ne sait pas factoriser efficacement les entiers, mais l'algorithme d'Euclide calcule le PGCD sans factoriser. On réduit alors le PPCM au PGCD via l'identité ppcm(x, y) = xy / pgcd(x, y).

// pgcd par Euclide, puis ppcm par réduction. O(log min(x, y)).
function pgcd(a: number, b: number): number {
  return b === 0 ? a : pgcd(b, a % b);
}

function ppcm(x: number, y: number): number {
  return (x / pgcd(x, y)) * y; // évite le dépassement
}

Enveloppe convexe vers tri. En envoyant chaque nombre x sur le point (x, x²) de la parabole y = x² (qui est convexe, donc chaque point est sur l'enveloppe), calculer l'enveloppe convexe revient à trier. Comme le tri a une borne inférieure Ω(n log n), l'enveloppe convexe hérite de cette borne : aucun algorithme ne peut la calculer plus vite.

NP-complétude : prouver la difficulté

Pour prouver qu'un problème est dur, on enchaîne les réductions depuis un problème déjà connu comme dur. Skiena nous demande d'abord d'accepter sur parole que le cycle hamiltonien (Hamiltonian cycle) et la couverture de sommets (vertex cover) sont durs, puis bâtit une chaîne.

Cycle hamiltonien vers TSP. Le cycle hamiltonien cherche une tournée passant une seule fois par chaque sommet d'un graphe non pondéré. On le réduit au TSP en construisant un graphe complet pondéré : les arêtes existantes pèsent 1, les autres 2. Un cycle hamiltonien correspond exactement à une tournée TSP de coût n.

// Réduction hamiltonien -> TSP décisionnel. O(n^2).
function reduireHamiltonienVersTsp(
  n: number,
  aretes: Set<string>, // "i,j" présentes dans G
): { poids: number[][]; seuil: number } {
  const poids: number[][] = [];
  for (let i = 0; i < n; i++) {
    poids.push([]);
    for (let j = 0; j < n; j++) {
      poids[i].push(aretes.has(`${i},${j}`) ? 1 : 2);
    }
  }
  return { poids, seuil: n }; // tour <= n  <=>  cycle hamiltonien
}

Couverture de sommets et ensemble indépendant. Une couverture de sommets est un petit ensemble S qui touche chaque arête. Un ensemble indépendant (independent set) est un ensemble de sommets sans aucune arête entre eux. Ces deux problèmes sont les deux faces d'une même pièce : si S est une couverture, alors V − S est un ensemble indépendant. La réduction est immédiate : VertexCover(G, k) équivaut à IndependentSet(G, |V| − k). On transforme l'entrée, jamais la solution.

Ensemble indépendant vers clique. Une clique est un sous-graphe complet (toutes les arêtes présentes). En complémentant le graphe (échanger arêtes et non-arêtes), un ensemble indépendant devient une clique. La chaîne est maintenant constituée : vertex cover → independent set → clique se transmettent leur difficulté.

Satisfiabilité : la mère de tous les problèmes durs

Toute la chaîne doit commencer par un problème universellement reconnu comme dur. C'est la satisfiabilité (satisfiability, SAT).

Problème : satisfiabilité. Entrée : un ensemble de variables booléennes V et un ensemble de clauses C. Sortie : existe-t-il une affectation de vrai/faux aux variables telle que chaque clause contienne au moins un littéral vrai ?

Par exemple, C = {{v₁, ¬v₂}, {¬v₁, v₂}} se satisfait avec v₁ = v₂ = vrai. Mais C = {{v₁, v₂}, {v₁, ¬v₂}, {¬v₁}} n'a aucune solution. Pour des raisons à la fois sociales et techniques, il est universellement admis que SAT est dur : tous les meilleurs experts du monde ont tenté un algorithme polynomial, tous ont échoué.

3-SAT : la frontière polynomial/dur

Une clause à un seul littéral est triviale à satisfaire. La transition vers la difficulté survient à trois littéraux par clause : c'est 3-SAT. On réduit SAT à 3-SAT en remplaçant chaque clause par des clauses de longueur exactement 3 (ajout de variables auxiliaires en chaîne), sans changer la satisfiabilité. Le même procédé prouve que tout k-SAT avec k ≥ 3 est dur. Fait remarquable, il s'effondre pour 2-SAT, que l'on résout en temps linéaire par parcours en profondeur sur un graphe adapté.

Une réduction créative : 3-SAT vers couverture de sommets

Comment fabriquer un graphe et une borne k à partir de variables et de clauses ? On construit deux types de gadgets. Pour chaque variable vᵢ, on crée deux sommets vᵢ et ¬vᵢ reliés par une arête (un sommet au moins par paire est requis : n sommets). Pour chaque clause de 3 littéraux, on crée un triangle (deux sommets au moins par triangle : 2c sommets). Enfin, on relie chaque sommet de triangle au sommet-variable du même littéral. Le graphe admet alors une couverture de taille n + 2c si et seulement si la formule est satisfiable.

3-SAT  {{v1, ¬v3, ¬v4}, {¬v1, v2, ¬v4}}
   gadgets variables : v1-¬v1, v2-¬v2, v3-¬v3, v4-¬v4  (4 aretes)
   gadgets clauses   : 2 triangles  (3 sommets chacun)
   aretes croisees   : chaque coin de triangle -> son littéral
   => couverture de taille n + 2c  <=>  formule satisfiable

Cette réduction illustre des propriétés générales : elle préserve la structure du problème sans le résoudre ; les instances produites ne forment qu'un sous-ensemble de toutes les instances possibles, mais cela suffit ; et elle capture l'essence de la difficulté — ici, le fait que satisfaire un jeu de contraintes est dur.

P vs NP : la grande question ouverte

La question « P = NP ? » est le problème ouvert le plus profond de l'informatique, doté d'un prix d'un million de dollars. Son enjeu : vérifier une solution est-il vraiment plus facile que d'en découvrir une ?

Pour les problèmes vus ici, vérifier semble trivial. Donné l'ordre des sommets d'une tournée, on additionne les poids des arêtes pour vérifier que leur somme est ≤ k. Donné une affectation, on parcourt chaque clause pour vérifier qu'un littéral est vrai. Le hic : personne n'a prouvé qu'on ne peut pas aussi les résoudre vite. Le certificat (certificate) — la solution candidate — se vérifie en temps polynomial.

// Vérificateur de certificat pour vertex cover. O(m).
function verifieCouverture(
  aretes: [number, number][], // m arêtes
  couverture: Set<number>, // le certificat
  k: number,
): boolean {
  if (couverture.size > k) return false;
  return aretes.every(([u, v]) =>
    couverture.has(u) || couverture.has(v),
  );
}

P est le club des problèmes résolubles en temps polynomial (plus court chemin, arbre couvrant minimal…). NP est le club, moins exclusif, des problèmes dont une solution se vérifie en temps polynomial — il contient TSP, SAT, vertex cover. Tout membre de P entre gratuitement dans NP (résoudre, c'est vérifier). La question à un million : existe-t-il dans NP un problème qui ne sera jamais dans P ? Si non, P = NP ; si oui, P ≠ NP. La quasi-totalité des spécialistes pensent que P ≠ NP, sans preuve.

Pourquoi SAT est la mère de tous

Le théorème de Cook-Levin est une super-réduction qui ramène tout problème de NP à la satisfiabilité. Conséquence : si l'on trouvait un algorithme polynomial pour SAT — ou pour n'importe quel problème NP-complet —, alors tous les problèmes de NP basculeraient dans P, et P = NP. Tout domino qui tombe les fait tous tomber. Notre incapacité collective à faire tomber le moindre est une raison forte de croire qu'ils sont tous vraiment durs.

Classe	Définition	Exemples
P	Résoluble en temps polynomial	Plus court chemin, arbre couvrant minimal
NP	Vérifiable en temps polynomial via un certificat	TSP, SAT, vertex cover (et tout P)
NP-difficile	Au moins aussi dur que tout problème de NP	SAT, échecs, arrêt d'un programme
NP-complet	NP-difficile et dans NP	SAT, vertex cover, cycle hamiltonien

S'en sortir face à un problème dur

Prouver qu'un problème est NP-complet n'est jamais la fin de l'histoire pour le praticien : l'application qui vous a amené là ne disparaît pas. Vous savez seulement que vous ne trouverez pas d'algorithme à la fois exact, rapide et général. Il vous reste trois leviers :

• Algorithmes rapides en moyenne : retour sur trace (backtracking) avec un élagage agressif, exponentiel dans le pire cas mais acceptable sur petites entrées ou cas particuliers.
• Heuristiques : recuit simulé, approches gloutonnes — rapides, mais sans aucune garantie sur la qualité.
• Algorithmes d'approximation (approximation algorithms) : ils renvoient une solution assortie d'une garantie prouvée : l'optimum ne peut jamais être bien meilleur. Souvent simples, rapides et faciles à coder.

Approximation 2 pour la couverture de sommets

Trouver la couverture de sommets minimale est NP-complet, mais un procédé d'une simplicité désarmante en trouve une au plus deux fois plus grande que l'optimum : tant qu'il reste une arête (u, v) non couverte, ajoutez u et v à la couverture, puis supprimez toutes les arêtes incidentes.

// Approximation 2 de vertex cover. O(m).
function couvertureApprochee(
  aretes: [number, number][],
): Set<number> {
  const cover = new Set<number>();
  const couverte = new Array(aretes.length).fill(false);
  for (let i = 0; i < aretes.length; i++) {
    if (couverte[i]) continue;
    const [u, v] = aretes[i];
    cover.add(u); // prendre LES DEUX extrémités
    cover.add(v); // est crucial pour la garantie
    for (let j = 0; j < aretes.length; j++) {
      const [a, b] = aretes[j];
      if (a === u || a === v || b === u || b === v) {
        couverte[j] = true;
      }
    }
  }
  return cover;
}

Pourquoi le facteur 2 ? Les arêtes sélectionnées forment un couplage (matching) : elles ne partagent aucun sommet. Toute couverture, même optimale, doit inclure au moins un sommet par arête sélectionnée. Notre couverture en prend deux par arête : elle est donc au plus deux fois l'optimum.

Approximation 2 pour le TSP métrique

Quand les distances respectent l'inégalité triangulaire (triangle inequality) — d(u, w) ≤ d(u, v) + d(v, w), vraie en géométrie euclidienne —, on approxime le TSP par un arbre couvrant minimal (minimum spanning tree, MST).

1. Calculer le MST T du graphe.   (borne inf. : poids(MST) <= tour optimal)
2. Parcours en profondeur de T : chaque arête est empruntée 2 fois.
   1-2-1-3-5-8-5-9-5-3-6-3-1-4-7-10-7-11-7-4-1   (coût <= 2 * optimal)
3. Raccourcis : sauter les sommets déjà visités.
   1-2-3-5-8-9-6-4-7-10-11-1   (inégalité triangulaire => coût réduit)

Le raisonnement tient en trois temps. D'abord, le poids du MST minore le tour optimal : retirer une arête d'une tournée donne un chemin (un arbre), donc au moins aussi lourd que le MST. Ensuite, un parcours en profondeur emprunte chaque arête de l'arbre deux fois, soit au plus deux fois l'optimum. Enfin, en prenant des raccourcis vers le prochain sommet non visité, l'inégalité triangulaire garantit que le tour ne peut que raccourcir. Le tour final est donc à un facteur 2 de l'optimum. Sans inégalité triangulaire, aucune approximation n'est connue.

Quand 2 n'est pas atteignable

Tout ne s'approxime pas à un facteur 2. La clique maximale ne s'approxime à aucun facteur intéressant. La couverture d'ensembles (set cover) — généralisation de vertex cover — occupe un entre-deux : l'heuristique gloutonne (choisir à chaque pas le sous-ensemble couvrant le plus d'éléments encore découverts) garantit un facteur Θ(lg n), et ce facteur logarithmique est une propriété du problème, pas une faiblesse de l'analyse. Connaître ces bornes par problème est l'objet du catalogue.

À retenir

• Les réductions sont l'unique outil : transformer A en B préserve la difficulté. Si B est facile alors A l'est ; si A est dur alors B l'est. Attention au sens : pour prouver qu'une cible est dure, partez d'un problème connu comme dur.
• NP, c'est la vérifiabilité en temps polynomial via un certificat ; P, la résolution polynomiale. La question P = NP ? reste ouverte, et l'opinion dominante est P ≠ NP.
• La satisfiabilité est la mère de tous les problèmes durs : le théorème de Cook-Levin y ramène tout NP. Un domino qui tombe les fait tous tomber. La chaîne classique va de 3-SAT à vertex cover, independent set, clique, hamiltonien…
• « NP-complet » signifie en pratique : cessez de chercher un algorithme exact et rapide et général. Reformulez plutôt le problème.
• Pour s'en sortir : exponentiel acceptable sur petites entrées, cas particuliers polynomiaux, heuristiques sans garantie, et surtout algorithmes d'approximation avec garantie prouvée.
• L'approximation 2 de vertex cover (prendre les deux extrémités d'une arête non couverte) et le TSP métrique 2-approché via MST sont simples, rapides, et bornés par construction. Lancez approximation et heuristique, gardez le meilleur.