Algorithmique

Les limites de l'algorithmique

Certains problèmes se résolvent en un clin d'œil, d'autres réclameraient plus de temps que l'âge de l'Univers, et quelques-uns ne seront jamais résolus par aucun programme. Cinq planches pour voir où passent ces frontières, et pourquoi.

La carte des territoires

Un algorithme est une suite d'instructions précises qui, à partir de données, fournit un résultat en un nombre fini d'étapes. La question de cette page n'est pas « comment écrire un algorithme ? » mais « existe-t-il toujours un algorithme, et un algorithme assez rapide ? ». La réponse découpe les problèmes en trois grands territoires.

Problèmes décidables — un programme finit toujours par donner la bonne réponse

NP — une solution proposée se vérifie vite

Sudoku, coloriage de carte, emploi du temps, voyageur de commerce (version « existe-t-il une tournée de moins de L km ? »), satisfaisabilité…

P — une solution se trouve vite

Trier, chercher un plus court chemin, calculer un PGCD, tester si un nombre est premier, colorier avec deux couleurs…

Au-delà de NP

Décidables, mais à un prix démesuré même pour vérifier : dire qui gagne aux échecs ou au go sur un plateau n × n demande un temps exponentiel, et cela est démontré.

Problèmes indécidables — aucun programme ne peut y répondre dans tous les cas

Le problème de l'arrêt (ce programme s'arrêtera-t-il ?), le dixième problème de Hilbert (cette équation à coefficients entiers a-t-elle une solution entière ?), le pavage du plan par un jeu de tuiles donné…

« Vite » a ici un sens précis : le nombre d'opérations est borné par un polynôme de la taille n des données (n, n², n³…). La grande question ouverte est de savoir si la zone verte remplit toute la zone orange : c'est le problème P = NP ?, mis à prix un million de dollars depuis l'an 2000.

Planche 1

Facile ou difficile ? Tout dépend de la croissance

Un problème est dit facile quand le travail grandit raisonnablement avec la taille n des données, difficile quand il s'emballe. On mesure ce travail par la complexité : le nombre d'opérations élémentaires en fonction de n. Réglez n et la vitesse de la machine : chaque barre donne le temps de calcul, sur une échelle où chaque graduation multiplie le temps par dix.

Taille des données n Vitesse de la machine

Temps de calcul pour la taille n choisie. Les traits pointillés donnent des repères humains et cosmiques.

Nombre d'opérations (en puissances de dix) selon n. n n log₂ n n² n³ 2ⁿ n! — la zone rosée dépasse un jour de calcul.

Opérations possibles en un jour

Plus grand n traitable en un jour, coût n² → machine 1000 fois plus rapide

Même question, coût 2ⁿ

Même question, coût n!

Ce qu'il faut retenir. Devant un coût polynomial, une machine mille fois plus rapide traite des données bien plus grosses (environ 31,6 fois plus pour n², car √1000 ≈ 31,6). Devant un coût exponentiel, elle ne gagne qu'une dizaine d'unités sur n (log₂ 1000 ≈ 9,97), et devant une factorielle deux ou trois à peine. Le progrès du matériel ne sauve donc pas un algorithme exponentiel : seule une meilleure idée le peut. C'est pourquoi la frontière entre « facile » et « difficile » est placée entre le polynomial et l'exponentiel.

Planche 2

L'explosion combinatoire : le partage du butin

Deux associés veulent se partager n objets de valeurs différentes en deux parts aussi égales que possible. La méthode naïve, dite de force brute, essaie tous les partages. Or chaque objet va soit dans la part A, soit dans la part B : chaque objet supplémentaire double le nombre de partages. C'est cela, l'explosion combinatoire : le nombre de cas à examiner croît beaucoup plus vite que la taille du problème.

Nombre d'objets n

À gauche le partage en cours d'examen, à droite le meilleur trouvé jusqu'ici. Le premier objet reste dans la part A : échanger les deux parts ne donne pas un partage nouveau.

L'arbre des choix : à chaque niveau un objet part à gauche (A) ou à droite (B). Le chemin rouge est le partage en cours.

Partages à examiner : 2ⁿ⁻¹

Partages examinés

Meilleur écart trouvé par la force brute

Contrôle : écart minimal par la table des sommes atteignables

Force brute à un milliard de partages par seconde

Ce qu'il faut retenir. Avec 24 objets, l'ordinateur passe encore en revue les 8 388 608 partages sous vos yeux. Avec 60 objets il lui faudrait des années, avec 100 objets plus de mille fois l'âge de l'Univers : le mur arrive brutalement. Le contrôle en vert emploie une autre idée (noter, objet après objet, toutes les sommes que l'on sait former) : il est rapide ici parce que les valeurs sont de petits entiers, mais il s'effondre à son tour quand les valeurs ont beaucoup de chiffres. Personne ne connaît de méthode rapide dans tous les cas.

Planche 3

Trouver ou vérifier : les classes P et NP

Voici un réseau de points reliés par des traits. Le défi : colorier chaque point avec l'une de trois couleurs sans que deux points reliés portent la même. Cliquez sur les points pour changer leur couleur et essayez. Puis comparez deux tâches très différentes : vérifier un coloriage proposé (il suffit de regarder chaque trait une fois) et en trouver un (la machine tâtonne, avance, se trompe, revient en arrière).

Nombre de points n Réseau

Un trait rouge épais signale deux voisins de même couleur. Pendant la recherche, le point entouré est celui que la machine essaie de colorier.

Vérifier votre coloriage : nombre de traits à regarder

Verdict de la vérification

Recherche par essais et retours en arrière

Coloriages imaginables : 3ⁿ

Contrôle : coloriages valides, comptés un par un

Avec deux couleurs seulement (parcours de proche en proche)

P est la classe des problèmes dont on sait trouver la réponse en temps polynomial. NP est celle des problèmes dont une réponse « oui », accompagnée d'une preuve (ici le coloriage lui-même, appelé certificat), se vérifie en temps polynomial. Tout problème de P est dans NP : qui sait trouver sait vérifier. La réciproque est la question ouverte. Attention au faux ami : NP ne veut pas dire « non polynomial » mais « polynomial sur une machine non déterministe », c'est-à-dire une machine imaginaire qui devinerait la bonne solution du premier coup.

Ce qu'il faut retenir. Vérifier coûte autant d'opérations qu'il y a de traits ; chercher peut coûter un nombre d'essais qui explose avec n, surtout quand il faut prouver qu'aucun coloriage n'existe (réseau « piégé »). Avec deux couleurs, en revanche, tout est facile : la couleur du premier point impose de proche en proche celle de tous les autres. Passer de deux à trois couleurs fait basculer le problème de P vers les problèmes les plus durs de NP, dits NP-complets : si l'on savait colorier vite avec trois couleurs, on saurait résoudre vite tous les problèmes de NP.

Planche 4

Faux jumeaux et seuil de difficulté

Le problème de référence de la classe NP s'appelle SAT (satisfaisabilité). On dispose de n interrupteurs (vrai / faux) et de m contraintes, chacune exigeant qu'au moins un interrupteur parmi quelques-uns soit dans une position donnée ; peut-on les satisfaire toutes ? Avec deux interrupteurs par contrainte (2-SAT) le problème est dans P ; avec trois (3-SAT) il est NP-complet. La page fabrique ici des problèmes au hasard et les résout réellement, pour mesurer où ils deviennent durs.

Problème Interrupteurs n

En abscisse, le nombre de contraintes par interrupteur α = m/n. proportion de problèmes qui ont une solution (échelle de gauche) effort médian de recherche, en nombre d'embranchements explorés (échelle de droite). Trait gris : seuil connu pour n infini.

Problèmes fabriqués et résolus

Rapport α où un problème sur deux a une solution

Sommet de l'effort médian

Solutions annoncées, revérifiées contrainte par contrainte

Contrôle : verdict comparé à l'essai des 2ⁿ positions (n = 10)

Des faux jumeaux : presque le même énoncé, deux mondes

Facile (dans P)	Difficile (NP-complet)	Ce qui change
Colorier un réseau avec 2 couleurs	Colorier un réseau avec 3 couleurs	Avec 2 couleurs, chaque choix impose le suivant ; avec 3, il reste une liberté à chaque pas.
2-SAT	3-SAT	Même phénomène : deux interrupteurs se contraignent en chaîne, trois non.
Circuit passant une fois par chaque rue (Euler)	Circuit passant une fois par chaque carrefour (Hamilton)	Euler se décide en comptant les rues à chaque carrefour ; pour Hamilton on ne connaît aucun critère simple.
Plus court chemin entre deux villes	Plus long chemin sans repasser par une ville	Un plus court chemin se construit de proche en proche ; pas un plus long.
Marier des paires compatibles	Former des trios compatibles	De deux à trois, encore.

Ce qu'il faut retenir. « NP-complet » ne veut pas dire que chaque exemple est dur. Avec peu de contraintes, presque tout convient et une solution se trouve tout de suite ; avec beaucoup, les contradictions sautent aux yeux. Les cas coriaces se concentrent dans une bande étroite, là où le problème hésite entre possible et impossible, et l'effort y grimpe quand n augmente (essayez n = 10 puis 50). Pour 2-SAT, la même expérience ne montre aucune montagne : l'effort reste modeste partout (une quinzaine d'embranchements au plus pour n = 50, contre plus de cent cinquante pour 3-SAT).

Planche 5 · signature

L'indécidable : le problème de l'arrêt

Jusqu'ici, les problèmes étaient durs mais solubles avec assez de temps. Voici une limite d'une autre nature. Le problème de l'arrêt demande un programme-oracle H qui, recevant le texte de n'importe quel programme et ses données, répondrait à coup sûr : « il s'arrêtera » ou « il tournera sans fin ». Alan Turing a démontré en 1936 qu'un tel programme ne peut pas exister. Un problème sans algorithme est dit indécidable.

Un programme de trois lignes suffit pour sentir la difficulté. Partez d'un entier ; s'il est pair, divisez-le par 2 ; sinon, multipliez-le par 3 et ajoutez 1 ; recommencez jusqu'à tomber sur 1. C'est la suite de Syracuse. Ce programme s'arrête-t-il pour tout entier de départ ? Personne ne le sait.

tant que n ≠ 1 :
    si n est pair :  n ← n / 2
    sinon :          n ← 3n + 1

Entier de départ

Le « vol » de l'entier choisi : valeur atteinte à chaque étape (échelle verticale en puissances de dix).

Durée du vol (étapes avant 1)

Altitude maximale

Plus long vol pour un départ inférieur à 10 000

Départs de 1 à 100 000 essayés par cette page

Ce que cela montre. Rien, dans le texte du programme, ne laisse prévoir la durée du vol : 26 s'arrête en 10 étapes, 27 en 111 après être monté à 9232. Le seul moyen général que l'on connaisse est de lancer le programme et d'attendre. S'il s'arrête, on le sait ; s'il ne s'arrête pas, on ne le saura jamais en attendant. Tous les entiers essayés par les mathématiciens (bien au-delà de 10²⁰) finissent sur 1, mais cela ne prouve rien pour les autres. Précisons que la conjecture de Syracuse elle-même n'est pas démontrée indécidable ; elle illustre seulement à quel point la question « s'arrête-t-il ? » peut résister.

Première idée : la diagonale. Un programme est un texte, et un texte peut être donné en entrée à un autre programme (un compilateur fait cela tous les jours). Rangeons tous les programmes en lignes, P₁, P₂, P₃…, et les mêmes textes en colonnes. Si l'oracle H existait, il saurait remplir chaque case : le programme de la ligne s'arrête-t-il sur l'entrée de la colonne ? Fabriquons alors un programme D qui, sur chaque entrée Pₖ, fait le contraire de ce que fait Pₖ sur son propre texte.

Taille du tableau

A = s'arrête, ∞ = tourne sans fin (tableau tiré au hasard, pour l'exemple). La ligne D inverse la diagonale : elle diffère donc de chaque ligne en une case au moins.

Lignes dont D diffère (sur la case diagonale)

D peut-il être l'une des lignes ?

Seconde idée : le piège. Pourtant, si H existait, D serait un vrai programme, très court, donc présent quelque part dans la liste. Que se passe-t-il quand on lui donne son propre texte ? Choisissez la réponse de H et suivez le chemin.

programme D(texte) :
    si H(texte, texte) répond « s'arrête » :  tourner sans fin
    sinon :                                    s'arrêter

Conclusion

Ce que cela montre. Quelle que soit sa réponse, H se trompe sur D. Comme D se construit en trois lignes à partir de H, c'est H qui ne peut pas exister. Ce n'est pas une affaire de puissance ou de patience : aucun ordinateur, aussi rapide soit-il, aucun langage, aucune astuce future n'y changera rien. Conséquence pratique : aucun outil ne peut garantir, pour tout programme, qu'il ne « plantera » pas dans une boucle infinie ; les vérificateurs de logiciels doivent se contenter de répondre « oui », « non » ou « je ne sais pas ».

Une machine de Turing est l'ordinateur le plus simple qui soit : un ruban de cases (0 ou 1), une tête qui lit une case, et quelques états. Selon l'état et le symbole lu, elle écrit, se déplace d'une case et change d'état. Le castor affairé à n états est la machine qui, partant d'un ruban vide, travaille le plus longtemps avant de s'arrêter. Son nombre de pas se note S(n).

Machine

Le ruban au fil du temps : chaque ligne est un instant (le temps descend), cases noires = 1, point rouge = tête de lecture. Pour la machine à 5 états, l'image est condensée : chaque ligne résume environ 118 000 pas.

Toutes les machines à n états, lancées une à une : nombre de machines qui s'arrêtent exactement au pas indiqué (échelle verticale en puissances de dix).

Machine lancée : pas effectués

Nombre de 1 sur le ruban

Valeurs démontrées S(n) et Σ(n)

Énumération : machines essayées

Record de durée et record de 1 parmi celles qui s'arrêtent

Arrêtées · sans instruction d'arrêt · encore en marche après 50 pas

Ce que cela montre. S(2) = 6, S(3) = 21, S(4) = 107, S(5) = 47 176 870 (démontré en 2024 seulement, après quarante ans d'efforts), et S(6) dépasse tout ce que l'on peut écrire avec des puissances empilées. Pourquoi cette folie ? Si l'on savait calculer S(n), on résoudrait le problème de l'arrêt : il suffirait de laisser tourner une machine S(n) pas, et de conclure qu'elle ne s'arrêtera jamais si elle tourne encore. Puisque l'arrêt est indécidable, la fonction S n'est calculable par aucun programme : elle finit par dépasser toute fonction calculable. Dans l'énumération, les machines « encore en marche » sont le cœur du problème : la simulation ne peut pas dire si elles s'arrêteront plus tard. Pour 2 et 3 états, des mathématiciens l'ont établi machine par machine, à la main ; aucune méthode générale ne le fera pour tout n.

Repères historiques

1928 — David Hilbert pose le « problème de la décision » : existe-t-il un procédé mécanique tranchant toute question mathématique ?
1931 — Kurt Gödel : dans toute théorie assez riche, il existe des énoncés vrais mais indémontrables.
1936 — Alan Turing définit sa machine et prouve que le problème de l'arrêt est indécidable ; Alonzo Church aboutit la même année par une autre voie. La réponse à Hilbert est non.
1962 — Tibor Radó invente le jeu du castor affairé, première fonction explicitement non calculable.
1965 — Alan Cobham et Jack Edmonds proposent d'appeler « efficaces » les algorithmes en temps polynomial : naissance de la classe P.
1970 — Youri Matiiassevitch achève la preuve que le dixième problème de Hilbert (équations en nombres entiers) est indécidable.
1971 — Stephen Cook, puis Leonid Levin indépendamment : SAT est NP-complet.
1972 — Richard Karp montre que 21 problèmes classiques sont NP-complets ; on en connaît aujourd'hui des milliers.
2000 — « P = NP ? » devient l'un des sept problèmes du millénaire de l'institut Clay.
2002 — Agrawal, Kayal et Saxena : tester si un nombre est premier est dans P.
2024 — Une équipe internationale de bénévoles démontre, preuve vérifiée par ordinateur, que S(5) = 47 176 870.

En trois idées

Facile : P

Le travail croît comme un polynôme de la taille des données. Une machine plus rapide permet de traiter nettement plus gros.

Difficile : NP-complet

On sait vérifier vite une solution, mais on ne sait la trouver qu'en explorant un nombre de cas qui explose. Personne n'a prouvé qu'on ne peut pas faire mieux.

Impossible : indécidable

Aucun programme ne répond correctement dans tous les cas, quel que soit le temps accordé. C'est démontré, une fois pour toutes.

Pour aller plus loin

Que fait-on face à un problème NP-complet ? On ne renonce pas : on se contente d'une solution approchée à quelques pour cent près, on exploite la structure particulière des cas réels, ou l'on emploie des solveurs qui, comme à la planche 4, sont rapides en dehors de la bande critique. Les solveurs SAT industriels traitent des millions de variables.

Une difficulté utile. La cryptographie repose sur des problèmes que l'on croit durs : multiplier deux grands nombres premiers est facile, retrouver les facteurs à partir du produit ne l'est pas (à notre connaissance). La factorisation est dans NP, mais on ne pense pas qu'elle soit NP-complète.

Et si P = NP ? Alors trouver serait à peu près aussi facile que vérifier : la plupart des codes secrets tomberaient, et l'optimisation deviendrait une routine. La grande majorité des chercheurs pense que P ≠ NP, sans savoir le démontrer.

Le théorème de Rice (1953) généralise le problème de l'arrêt : toute question non triviale sur ce que calcule un programme (rend-il toujours 0 ? deux programmes font-ils la même chose ?) est indécidable.