#Complexité des problèmesCopier le lien

Prérequis: notations asymptotiques et modèle RAM (chapitre Complexité des algorithmes), graphes et parcours (BFS, DFS).

Objectifs:

• Classer des problèmes (et non plus des algorithmes) par difficulté intrinsèque.
• Manipuler les définitions de P, NP, NP-complet et les réductions polynomiales.
• Reconnaître un problème NP-complet en pratique et choisir une parade argumentée.

#Du coût d'un algorithme au coût d'un problèmeCopier le lien

Les chapitres précédents analysent des algorithmes: celui-ci analyse des problèmes. La question n'est plus « combien coûte cet algorithme ? » mais « existe-t-il un algorithme efficace pour ce problème, quel qu'il soit ? ». La théorie de la complexité classe les problèmes selon les ressources minimales nécessaires, et cette classification borne ce que l'ingénieur peut espérer: si un problème est NP-complet, chercher un algorithme polynomial exact est probablement perdu, et le travail pertinent change de nature.

#Problèmes de décisionCopier le lien

Un problème de décision prend une entrée et répond OUI ou NON. C'est le format de travail de la théorie de la complexité.

Exemples:

• SAT: une formule booléenne donnée admet-elle une affectation de ses variables qui la rende vraie?
• CLIQUE: un graphe G contient-il une clique (sous-graphe complet) de taille au moins k?
• CIRCUIT-HAM: G contient-il un circuit hamiltonien (passant par chaque sommet exactement une fois)?

Tout problème d'optimisation se ramène à une famille de problèmes de décision: « existe-t-il une solution de coût ≤ k ? » avec k en entrée. Si l'on sait décider pour chaque k, on sait optimiser par recherche sur k (dichotomie sur l'espace des coûts).

#Classe PCopier le lien

P regroupe les problèmes de décision résolubles en temps polynomial par une machine déterministe:

Exemples dans P: le tri (vérifier qu'un tableau est trié, ou le trier, est polynomial), le plus court chemin (Dijkstra, Floyd-Warshall), l'arbre couvrant minimum (Kruskal, Prim), le test de primalité (AKS, 2002, en temps polynomial déterministe), la programmation linéaire (points intérieurs).

La thèse (informelle) derrière la classe: polynomial = efficacement résoluble. Justification pratique: la table du chapitre précédent montre qu'au-delà du polynomial, les tailles praticables s'effondrent. Justification théorique: les polynômes se composent (un algorithme polynomial qui appelle un autre polynomial en sous-routine reste polynomial), ce qui en fait la plus petite classe stable par composition.

#Classe NPCopier le lien

NP (Non-deterministic Polynomial) regroupe les problèmes de décision dont une réponse OUI peut être vérifiée en temps polynomial, étant donné un certificat de taille polynomiale.

Formellement: L ∈ NP s'il existe un vérificateur V polynomial tel que x ∈ L si et seulement s'il existe un certificat c avec V(x, c) = OUI. La définition est asymétrique: elle ne demande de vérifier que les instances positives.

Exemples:

• SAT: certificat = une affectation des variables; vérification = évaluer la formule, O(longueur).
• CLIQUE: certificat = la liste des k sommets; vérification = contrôler que toutes les paires sont adjacentes, O(k²).
• COMPOSITE (un nombre est-il composé ?): certificat = un facteur non trivial; vérification = une division.

Propriété immédiate: , puisqu'un problème résoluble en temps polynomial est vérifiable en temps polynomial (le vérificateur ignore le certificat et résout le problème). L'inclusion inverse est la question ouverte la plus célèbre de l'informatique: P = NP? (un des sept problèmes du millénaire, un million de dollars). Le consensus des chercheurs est P ≠ NP, mais aucune preuve n'existe.

#Réductions polynomialesCopier le lien

Une réduction polynomiale de A vers B, notée , est une fonction f calculable en temps polynomial telle que:

Autrement dit: transformer toute instance de A en instance équivalente de B, à coût polynomial. La réduction oriente la difficulté: si et si B ∈ P, alors A ∈ P (on transforme puis on résout). Contraposée utile: si A est réputé difficile et que , alors B est au moins aussi difficile.

La réduction est l'outil de travail central: c'est par chaînes de réductions que l'on prouve la NP-complétude, sans jamais toucher à la définition de NP.

#NP-complétudeCopier le lien

Un problème L est NP-complet si:

1. L ∈ NP (vérifiable en temps polynomial);
2. L est NP-difficile: pour tout , .

Théorème de Cook-Levin (1971): SAT est NP-complet. C'est la porte d'entrée: tout problème de NP se réduit à SAT. À partir de là, on n'utilise plus la définition: pour prouver L NP-complet, on montre L ∈ NP et on réduit un NP-complet connu vers L.

Exemple de réduction, INDEPENDENT-SET et VERTEX-COVER: un ensemble S de sommets est indépendant si et seulement si son complément V ∖ S est une couverture (toute arête a au moins une extrémité hors de S, donc dans le complément). D'où admet un indépendant de taille ≥ k ssi admet une couverture de taille ≤ |V| − k: réduction polynomiale dans les deux sens, les deux problèmes sont aussi difficiles l'un que l'autre.

#Au-delà: coNP, PSPACE, indécidabilitéCopier le lien

• coNP: complémentaires des problèmes de NP. TAUTOLOGIE (une formule est-elle vraie sous toute affectation?) est le complémentaire de SAT: il est dans coNP.
• PSPACE: problèmes solubles en espace polynomial. NP ⊆ PSPACE (une machine peut énumérer les certificats en réutilisant le même espace). Les jeux (generalized geography, certains puzzles) sont PSPACE-complets.
• EXPTIME: temps exponentiel. On a les inclusions , et au moins une est stricte (P ⊊ EXPTIME par le théorème de hiérarchie temporelle), sans savoir laquelle.
• Indécidabilité: le problème de l'arrêt (un programme donné s'arrête-t-il sur une entrée donnée?) n'est décidable par aucun algorithme, quel que soit le temps accordé (diagonalisation de Turing). Il est NP-difficile sans être dans NP: la hiérarchie du difficile ne s'arrête pas à NP.

#Implications pratiquesCopier le lien

Reconnaître un problème NP-complet en mission change le plan de travail. Les parades, par ordre de fiabilité:

1. Restreindre le problème: la contrainte qui rend le problème dur manque peut-être dans votre instance. 2-SAT est dans P (résoluble en temps linéaire par composantes fortement connexes) alors que 3-SAT est NP-complet; le plus court chemin avec poids positifs est polynomial, le voyageur de commerce exact non. Vérifier d'abord si votre cas particulier est couvert par une restriction polynomiale connue.
2. Taille réelle: un algorithme exponentiel reste praticable jusqu'à n ≈ 30 ou 40 selon la base. Recherche exacte par programmation dynamique sur les sous-ensembles (TSP: ) traite n = 20 en quelques secondes.
3. Approximation garantie: pour certains problèmes, un ratio d'approximation polynomial est démontrable (couverture de sommets: facteur 2 par le glouton sur les arêtes; TSP métrique: facteur 2 par arbres doubles, 3/2 par Christofides). Pour d'autres, toute approximation meilleure qu'un facteur donné est elle-même NP-difficile.
4. Heuristiques: recuit simulé, recherche locale, algorithmes génétiques. Aucune garantie formelle, mais souvent efficaces sur les instances réelles; à valider expérimentalement, jamais à présenter comme exactes.
5. Complexité paramétrée: si le paramètre k reste petit (clique de taille 10 dans un graphe d'un million de sommets), un algorithme FPT en reste praticable.

#Exercice 1: certificat et vérificateur pour HAMPATHCopier le lien

Donnez un certificat et un vérificateur polynomial pour CIRCUIT-HAM (le graphe contient-il un circuit passant par chaque sommet exactement une fois?).

Correction: certificat = une liste ordonnée des n sommets. Vérificateur: contrôler que la liste contient chaque sommet exactement une fois (table de booléens, O(n)), que chaque paire consécutive est une arête (n − 1 accès à la matrice d'adjacence, O(1) chacun), et que le dernier sommet est adjacent au premier (boucler le circuit). Total O(n²) avec la matrice, polynomial. Si le graphe admet un circuit hamiltonien, le certificat correspondant est accepté; sinon aucune liste ne passe tous les contrôles. C'est exactement la définition de l'appartenance à NP.

#Exercice 2: si SAT ∈ P alors P = NPCopier le lien

Démontrez l'implication.

Correction: supposons SAT résoluble en temps polynomial. Soit L un problème quelconque de NP. Par le théorème de Cook-Levin, : il existe une réduction f polynomiale telle que . Pour décider L sur l'entrée x: calculer f(x) (polynomial), puis appliquer l'algorithme polynomial de SAT (polynomial). La composition de deux polynômes est polynomiale, donc L ∈ P. Comme L était arbitraire dans NP, , et avec toujours vrai, P = NP. La structure de l'argument est la définition même de la NP-difficulté de SAT: c'est parce que tout NP se réduit à SAT qu'un algorithme polynomial pour SAT entraînerait l'effondrement des deux classes.

#Exercice 3: réduire VERTEX-COVER vers INDEPENDENT-SETCopier le lien

On rappelle l'équivalence: S indépendant de taille k dans G ⟺ V ∖ S couverture de taille |V| − k. Utilisez-la pour construire la réduction, puis discutez: que se passe-t-il si l'on réduit dans l'autre sens?

Correction: la réduction f prend (G, k) et produit (G, |V| − k). Elle est calculable en temps polynomial (compter les sommets). Correction de la réduction: (G, k) ∈ VERTEX-COVER s'il existe une couverture C de taille ≤ k; alors V ∖ C est indépendant de taille ≥ |V| − k, donc (G, |V| − k) ∈ INDEPENDENT-SET; réciproquement un indépendant I de taille ≥ |V| − k donne la couverture V ∖ I de taille ≤ k. L'équivalence étant symétrique, la réduction inverse existe aussi (prendre (G, k) → (G, |V| − k) de la même façon): les deux problèmes sont polynomiairement équivalents, et l'un est NP-complet si et seulement si l'autre l'est. Leçon générale: une paire de réductions mutuelles identifie des problèmes de même difficulté, c'est ainsi que se construisent les familles de problèmes NP-complets.