Résumé

Avant d'étudier à proprement parler la théorie de la complexité, il est légitime d'aborder au préa­la­ble la question de la calculabilité. L'algorithmique telle qu'elle est étudiée durant les premières années universitaires, avec son cortège d'algorithmes élémentaires ou sophistiqués, tend à instiller l'idée qu'il existe toujours un algorithme, fût-il médiocre, pour résoudre un problème. Les logiciens savent depuis près d'un siècle qu'il n'en est rien. Connaître les limites du calcul est incontournable pour un scien­ti­fi­que aujourd'hui et a fortiori pour un informaticien. Il doit être à même de dis­tin­guer les problèmes résolubles des autres et à défaut d'avoir conscience qu'il peut être confronté à des obstacles dé­fi­ni­ti­ve­ment infranchissables.

Même si cela peut paraître difficile à concevoir à ce stade, il existe de nombreux problèmes (un doux euphémisme pour désigner une infinité non-dénombrable) qui n'admettent aucun algorithme pour les résoudre. L'acception du terme aucun est ici celle des mathématiques, au même titre qu'il n'existe aucun nombre premier pair strictement supérieur à 2.

Il nous faudra préciser ce que l'on entend par problème et par algorithme. La machine de Turing prendra à ce stade le relais de la machine ram pour élaborer des raisonnements rigoureux. Ce mo­dè­le introduit en 1936 par le mathématicien anglais Alan Turing est bien antérieur à celui de la ma­chi­ne ram, il est plus rudimentaire mais a fait ses preuves, au sens propre comme au figuré. Sa simp­li­ci­té extrême a permis d'établir des résultats fondamentaux et en fait un outil théorique de choix pour aborder les questions sur la nature du calcul.

Une fois que le deuil aura été fait des problèmes incalculables, nous verrons qu'en terme d'efficacité la situation n'est guère meilleure pour les problèmes calculables. On considère qu'un algorithme est efficace pour résoudre un problème si sa fonction de complexité est majorée par une fonction po­ly­no­mia­le. À l'heure actuelle, nous ne disposons que d'algorithmes de complexité exponentielle voire pire, pour résoudre nombre de problèmes cruciaux dans des registres variés. Bien entendu, le fait de ne pas avoir trouvé d'algorithme efficace pour résoudre un problème ne signifie pas nécessairement qu'il n'en existe pas et il est extrêmement rare que l'on soit capable de le prouver ou encore d'établir une borne inférieure sur la complexité de tous les algorithmes qui pourraient le résoudre. Nous avons pu le faire en licence pour les algorithmes de tris dits comparatifs en prouvant que leur complexité est bornée inférieurement par une fonction linéarithmique (c'est-à-dire en \(\Omega(n\log n)\)) si \(n\) désigne le nombre de termes à trier (cf. borne sur les tris comparatifs).

Mais alors, comment mesurer la difficulté intrinsèque d'un problème si l'instrument de mesure n'opère pas sur le problème lui-même mais sur les algorithmes qui le résolvent et sans même tous les connaître ? Pour aborder cette question, on se limite*(*) on précisera pourquoi il ne s'agit pas réel­le­ment d'une li­mi­ta­tion aux problèmes de décision, autrement dit aux problèmes qui attendent une réponse positive ou négative. Par exemple, un nombre entier \(N\) donné est-il premier ? Dans un réseau social donné, peut-on trouver un sous-ensemble de 50 individus tous en relation les uns avec les autres ? Peut-on livrer leurs pizzas à des particuliers en parcourant moins que \(K\) kilomètres ?

C'est à ce stade que commence la classification. Un algorithme est dit polynomial si sa fonction de complexité (en temps ou en espace) est majorée par une fonction polynomiale, comme l'algorithme du tri à bulles ou l'algorithme du plus court chemin de Dijkstra. L'ensemble des problèmes de décision qui admettent un algorithme polynomial pour répondre à la question constitue la classe P. Pour les problèmes de décision qui résistent, c'est-à-dire ceux dont on ne sait pas encore s'ils sont polynomiaux ou non, on révise nos ambitions en cherchant un algorithme capable de vérifier une preuve que la réponse est positive en temps polynomial.

Par exemple on peut vérifier en temps polynomial qu'un nombre entier \(N\) est composé*(*) il se dé­com­po­se en un pro­duit de deux nom­bres non triviaux. en four­nis­sant comme preuve les deux nombres \(A>1\) et \(B>1\) tels que \(N=A\times B\). Il suffit pour vérifier cette preuve de calculer le produit \(A\times B\) à l'aide de l'algorithme de multiplication étudié au primaire et de le comparer à la valeur \(N\). Cet algorithme a une complexité quadratique puisqu'il demande \(n\times m\) opérations élémentaires si \(n\) et \(m\) désignent le nombre de chiffres de \(A\) et \(B\). L'algorithme étant polynomial, le problème entre dans la classe NP dite Non-déterministe Polynomial.

Grossièrement, la classe P collecte les problèmes pour lesquels on peut écrire une preuve (i.e. un algorithme) pour fournir la réponse et ceci en temps polynomial, alors que la classe NP collecte les problèmes pour lesquels on peut écrire un algorithme en temps polynomial qui vérifie une preuve (dite aussi certificat) fournie par ailleurs (en l'occurrence un oracle dans la terminologie de cette théorie). Intuitivement, il semble plus facile de vérifier une preuve que d'en trouver une. C'est la traduction de la fameuse conjecture P ≠ NP mise à prix par le claymath institute à $1.000.000. Faute de réponse à cette conjecture, il est d'un grand intérêt de se focaliser sur les problèmes les plus difficiles de la classe NP. Encore faut-il développer l'outil de mesure adéquat de cette supposée difficulté.

On introduit alors la notion de réduction polynomiale entre problèmes de décisions. On dit qu'un problème \(\Pi\) se transforme polynomialement en un problème \(\Pi'\), ce que l'on note \(\Pi\propto\Pi'\), s'il existe un algorithme polynomial \(T\) tel que pour toute instance \(I\) de \(\Pi\) l'instance \(T(I)\) de \(\Pi'\) est positive (i.e. la réponse à la question est oui) si et seulement si l'instance \(I\) de \(\Pi\) est positive. On montre immédiatement que la relation binaire de réduction constitue un préordre (réflexivité et transitivité), ainsi \(\Pi\propto\Pi'\) exprime formellement que \(\Pi\)' est plus difficile que \(\Pi\). En effet, une fois l'instance du problème \(\Pi\) traduite en instance du problème \(\Pi'\), on dispose de n'importe quel algorithme de ré­so­lu­tion du problème \(\Pi'\) pour résoudre le problème \(\Pi\). Bien entendu si \(\Pi'\) admet un algorithme po­ly­no­mial, il en sera de même pour \(\Pi\) puisque le coût de la traduction préalable est lui aussi polynomial.

On se pose alors la question de l'existence de problèmes plus difficiles que tous les autres ? C'est Stephen Cook qui répond à cette question en 1971 en démontrant qu'il existe de tels monstres dans la classe NP. Le problème séminal de cette classe est le problème sat (SATisfaisabilité de clauses). L'instance du problème est une formule logique fournie sous forme normale conjonctive. La question est de savoir si cette formule est satisfaisable, autrement dit s'il existe une instanciation des variables logiques qui permette de satisfaire la formule. Par exemple, la formule \((a\vee b\vee\overline{c})\wedge(\overline{a}\vee b)\) est sa­tis­fai­te dès que \(b\) est vrai (entre autres). La classe de ces problèmes au sommet de la hiérarchie est la classe NP-Complet. Notons que si l'on découvre un algorithme polynomial pour résoudre un problème quelconque de cette classe, on fait tomber tous les dominos par transitivité et ainsi on prouve que P=NP en empochant au passage le million de dollars.

Afin de dépasser les limites fixées par l'approche déterministe de la résolution des problèmes, l'idée logique est d'approximer la solution d'un problème plutôt que d'en chercher la valeur exacte. La dernière partie du cours introduit la classe PCP\(_{}[]\) _{c(n), s(n)}(r(n),s(n)) des problèmes pour lesquels il existe un algorithme non-déterministe polynomial randomisé tel que la machine accepte une instance positive \(I\) de longueur n pour une preuve fournie par l'oracle avec une probabilité au moins c(n) si \(I\) est positive et au plus s(n) quelle que soit la preuve fournie par l'oracle. La fonction r(n) correspond à la complexité en temps et s(n) au nombre de bits d'aléa utilisés. L'acronyme PCP signifie "Probabilisticaly Checkable Proof" (approximativement preuve vérifiable en probabilité).

Le résultat fondamental et magistral obtenu à l'aide de la théorie de l'approximation est le théorème PCP qui dit en substance que l'on peut se contenter de lire certaines parties d'une preuve pour s'as­su­rer de sa validité avec un degré de certitude arbi­trai­rement grand. La théorie de l'approximation a également permis de mettre en évidence des différences majeures entre les problèmes de la classe NP-complet. Il apparaît que si l'on se contente d'une approximation d'une solution à un problème d'optimisation, certains problèmes admettent des algorithmes polynomiaux (même si l'on impose une approximation arbitrairement proche de l'optimum !). Ceci rend ces problèmes bien moins in­ti­mi­dants en pratique quand bien même ils restent NP-complets. Cependant d'autres problèmes NP-complets restent redoutables comme le problème de la clique maximale : il s'agit de trouver dans un graphe un sous-graphe de taille maximale dont tous les sommets sont connectés entre eux (une clique). Pour un graphe donné et en notant \(K\) la taille d'une clique maximale, on montre que pour tout \(\epsilon>0\), l'existence d'un algorithme polynomial pour décider s'il existe une clique de taille su­pé­rieu­re à \(\epsilon K\) entrainerait P=NP.

Ordinateurs, calculs

Dans la riche histoire des techniques*(*) la technologie dé­si­gnant la science qui les étu­die. du xx-ème siècle, l'ordinateur est sans conteste l'outil qui a engendré les transformations les plus radicales de notre société. Aujourd'hui tout le monde utilise des ordinateurs, sans même parfois en avoir conscience tant il est polymorphe : téléphone cellulaire, carte bancaire, con­sole de jeux vidéo, lecteur bluray, etc.

Les avancées scientifiques et industrielles dans le domaine dit des technologies de l'information sont si rapides que l'on est en droit de se demander s'il existe une limite à la capacité de traitement des machines. De nombreux problèmes complexes peuvent aujourd'hui être résolus en quelques instants par un simple smartphone à 200€, là où il fallait un matériel volumineux et coûteux il y a seulement une trentaine d'années. Gordon Moore, l'un des trois co-fondateurs de la société Intel, avait affirmé en 1965 que la densité des transistors dans les microprocesseurs doublerait tous les deux ans (même si l'affirmation concernait les semi-conducteurs initialement). Cette conjecture, appelée aujourd'hui loi de Moore commence tout juste à être mise en défaut, 50 ans après. Deux questions viennent immédiatement à l'esprit : y-a-t-il une fin à cette progression ? Existe-t-il des problèmes qui ne peuvent être résolus par une machine ?

Pour la seconde question et si l'on accepte la conjecture de Moore, on peut légitimement penser qu'aucun problème n'est à l'abri d'une résolution par un ordinateur à condition d'être patient. À l'heure où j'écris ces lignes, les derniers processeurs amd cadencés à 5GHz sont capables de réaliser des milliards d'opérations par seconde, bien que les performances d'une machine dépendent de bien d'autres critères que le cadencement de l'horloge.

Nous montrerons dans ce cours que la réalité est à l'opposé de ce que ces révolutions permanentes nous portent à croire. L'infinie majorité des problèmes sont inaccessibles à quelque machine que ce soit. Il s'agit de la classe des problèmes incalculables (ou indécidables si la réponse au problème est oui ou non), autrement dit les problèmes pour lesquels il n'existe aucun algorithme pour les résou­dre.

L'incapacité définitive des machines à résoudre la majorité des problèmes indépendamment du temps, de leur puissance de traitement et de la mémoire dont elles disposent, est une idée encore assez peu répandue dans le grand public. Elle est l'aboutissement de plusieurs siècles de recherche en mathématiques et a radicalement modifié l'approche scientifique des questions qui restent encore sans réponse. En réalité cette conclusion n'est que la conséquence d'un résultat plus général qui dépasse de loin le simple fonctionnement des ordinateurs. Nous verrons pour cela qu'il existe des interactions étonnantes entre le raisonnement mathématique, l'algorithmique et les nombres. Pour revenir aux machines, il est très important de comprendre dès à présent que cette incapacité est structurelle, c'est la nature même de leur fonc­tion­ne­ment qui est en cause et ni le temps, ni la capacité de calcul n'y peuvent rien. Un des objectifs de ce cours est d'en convaincre le lecteur.

Une fois que l'on a fait le deuil de notre capacité à traiter tous les problèmes ou à répondre à toutes les questions, on s'attache à l'étude des rescapés pour distinguer ceux que l'on peut résoudre efficacement des autres. Là encore la conclusion de cette étude est négative, les problèmes les plus importants que l'on aimerait résoudre de manière efficace (terme à définir dans notre contexte) se montrent en fait inextricables. La sécurité du protocole de chiffrement à clef publique rsa repose sur la supposée difficulté à factoriser un nombre en produit de facteurs premiers. SUITE A REPRENDRE, ARTICULATION BANCALE AVEC LES PROPOS PRÉCEDENTS => Comme pour la calculabilité, il faudra être très méfiant avec notre intuition. Pour illustrer ce propos, considérons le problème de la primalité d'un entier \(N\). Tout le monde ou presque, sait qu'il est impossible dans la pratique de déterminer avec certitude si un entier \(N\) est premier ou non pour peu que celui-ci soit suffisamment grand, bien qu'il existe de nombreux algorithmes de factorisation (si l'on relaxe la notion de certitude la situation devient nettement moins dramatique, voir exercice 2 plus bas). Ici, c'est le temps qui est l'adversaire principal, ces algorithmes demandent beaucoup trop de temps pour résoudre le problème. Le système de chiffrement à clef publique rsa est entièrement basé sur cette difficulté à décomposer les nombres et est utilisé des millions de fois tous les jours pour réaliser des transactions sécurisées.

Pour conclure ce paragraphe, la théorie de la calculabilité-décidabilité ne se préoccupe pas de l'effectivité d'un calcul, les contingences matérielles et temporelle n'existent pas, la question centrale concerne l'existence d'un algorithme pour résoudre un problème. À l'opposé, la théorie de la complexité et la théorie de l'approximation se préoccupent du temps et de l'espace et cherchent à classifier les problèmes en terme de difficulté.

L'aspect positif de cette étude, et c'est certainement cela qu'il faudra retenir de ce cours, c'est que l'esprit humain est capable de prouesses remarquables. Les pionniers de l'informatique ont réussi à séparer ce que l'on peut traiter de manière automatique de ce que l'on ne peut pas traiter. Nous verrons que l'existence de problèmes incalculables tient en substance à l'existence d'ensembles infinis non-dénombrables.

Plan du cours

Le cours est décomposé en quatre parties. Après un bref rappel historique sur la notion de calculabilité, nous aborderons dans un premier temps plusieurs aspects des Mathématiques, qui, même s'ils paraissent a priori éloigné de notre sujet, sont tous indispensables à la compréhension de cette théorie. La logique sur laquelle repose les démonstrations sera brièvement évoquée et nous étudierons quelques éléments de la théorie axiomatique des ensembles de Zermello-Fraenkel-Skolem. Nous étudierons également les nombres et leurs représentations ainsi que la notion de cardinalité, notamment le concept d'infini.

Dans un deuxième temps, nous essaierons de définir ce qu'est un algorithme et de dégager des critères intuitifs et par conséquent informels pour la caractériser. Cette ébauche permettra de s'assurer que les différents modèles formels que nous étudierons les satisfont. Nous revisiterons brièvement le modèle de la machine ram déjà étudié en licence et nous présenterons le modèle de la machine de Turing. Pour illustrer la thèse de Church, nous étudierons sommairement l'équivalence des deux modèles, non pas parce que la preuve de cette équivalence contienne une quelconque difficulté technique, mais pour nous concentrer sur la machine de Turing.

Le modèle étant choisi, on aborde la question de la calculabilité, qui relève d'une certaine manière de la philosophie des machines, indépendamment des contingences matérielles et temporelles. Que peuvent-elles calculer ou décider ? À titre d'exemple, tout étudiant en informatique aimerait disposer d'un compilateur qui soit à même d'indiquer si son programme peut entrer dans une boucle infinie, ce qui permettrait d'éviter de fastidieuse séances de debuggage. Malheureusement, un tel compilateur n'existe pas. Il faut bien comprendre le sens de cette phrase, il n'est pas possible d'écrire un tel compilateur. Ce type de résultat peut paraître troublant, mais le lecteur devrait se sentir plus à l'aise à l'issue de ce cours dont c'est la finalité.

La troisième partie aborde la notion de complexité d'un algorithme (le mot complexité suffit à lui seul à donner une idée de ce que la notion signifie) et sera définie formellement à partir des machines de Turing abordées précédemment. La complexité tente de mesurer les performances des algorithmes, en terme de temps de calcul ou d'espace mémoire. Nous étudierons les grandes classes de problèmes P, NP, NP-complets et nous démontrerons le théorème de Cook pour conclure avec 6 grands problèmes de la classe NP-complet et quelques preuves de NP-complétude.

La dernière partie est une brève introduction à la théorie de l'approximation qui essaie d'outrepasser les limites fixées par la théorie de la complexité. Il s'agit cette fois de déterminer s'il est possible de trouver des algorithmes polynomiaux à des problèmes difficiles en relachant la contrainte d'exactitude, autrement dit si l'on s'autorise à répondre correctement à une question avec une certaine probabilité d'erreur.

Contexte historique

Les questions sur la nature du calcul se sont posées essentiellement dans le cadre des mathématiques pures. La rigueur et le formalisme sont, au regard de l'histoire des mathématiques, des développements très récents puisque c'est seulement à la fin du 19ème siècle que certains mathématiciens ont noté qu'il devenait nécessaire de travailler et de raisonner dans un cadre rigoureux.

Gottlob Frege (1848-1925) a tenté de développer un système de notation strict et précis pour formaliser les démonstrations mathématiques, mais il aboutit rapidement à la conclusion que le modèle aboutissait à des contradictions. Les mathématiciens de l'époque étaient convaincus que l'on pouvait tout démontrer, au sens où dans un système axiomatique, un problème, i.e. un théorème, pour peu que l'on soit assez ingénieux, devait être vrai (ou faux, mais il ne s'agit plus d'un théorème !)

Le célèbre David Hilbert (1862-1943) fut l'un des premiers mathématiciens à s'intérroger sur la nature d'une démonstration et d'un système axiomatique en mathématique ? Il pensait, à tort, que toute preuve, à condition d'être rédigée dans un système mathématique formel, pouvait être validée par un procédé mécanique, ou du moins pouvait l'être. Nous verrons qu'il n'en est rien. La raison tient essentiellement au concept d'ensemble infini et à la manière de les manipuler.

Cauchy et Weierstrass (1789--1857, 1815--1897) ont donné les moyens de manipuler l'infini en formalisant les notions de limite et de continuité et en réduisant les raisonnements à l'utilisation des désormais célèbres \(\eta\) et \(\epsilon\).

Cantor montre en 1873 qu'il faut distinguer plusieurs infinis \({\mathbf N}\) et \({\mathbf R}\) et construisit une théorie élégante des nombres transfinis en 1890, mais toutes les bases formelles pour manipuler ces nombres aboutissaient immanquablement à des contradictions. Cet article avait beaucoup marqué Hilbert qui y voyait un formidable moyen de clarifier les raisonnements : Personne ne nous conduira hors du paradis que Cantor à crée pour nous. Il reformula alors sa pensée au sujet des théorèmes :

1. Le mathématiciens allemand Gödel et l'américain Kleene (1909-1994) proposent la théorie des fonction partiellement récursives basée sur la notion de récurrence pour la définition des fonctions.
2. Les même auteurs et le français J. Herbrand (1908-1931) proposent les fonctions récursives générales définies à travers un mécanismes d'équations.
3. L'américain Alonzo Church (1903-1995) développe le \(\lambda\)-calcul basé sur les définitions récursives avec certains types de contraintes (c'est la base du langage Lisp).
4. L'anglais Alan Turing (1912-1954) donne un modèle théorique de calculateur. C'est aujourd'hui l'outil standard pour aborder ces questions.

Ces modèles étaient censés décrire ce que la pensée humaine était capable d'appréhender et qujourd'hui la thèse de Church est admise par tous les mathématiciens ou informaticiens. Les chercheurs en théorie de la programmation on donc pu caractériser précisément ce que l'on peut calculer ou non. Le résultat de ces recherches est dévastateur, comme nous le verrons, la plupart des fonctions ne sont pas calculables.

Une fois ces faits établis, les chercheurs ont porté leur attention sur la vcomplexité : en supposant qu'un problème est résoluble, de quelle manière peut-on le r\'seoudre efficacement ? La recherche opérationnelle développé durant la seconde guerre mondiale a montré qu'il fallait aussi être efficadce en temps de calcul. Les pionniers de la programmation furent incontestablement l'anglais Alan Turing et l'américain John Von Neumann (1903-1957) qui fut l'un des plus brillant mathématiciens de ce siècle. Aujourd'hui les machines sur lesquelles nous travaillons sont toutes du type Von Neumann (cpu, mémoire, bus...)

Dans les années 60, Hartmanis, Steams et d'autres ont commencé à définir et à caractériser des classes de problèmes en fonctions des ressources en espace et en temps nécessaires à leur résolution.

Cobham, Adwards ont orbservé que plusieurs problèmes étaient apparemment durs à résoudre mais avaient des solutions qui étaient très facile à valider, par exemple sur la primalité des nombres. Ce travail fut formalisé par Cook en 1971 qui démontra l'existence des problème NP-complets. Un an plus tard, R. Karp montre l'importance de cette notion en démontrant que \(20\) problèmes qui n'admettent pas de solutions efficaces sont équivalents en difficulté et appartiennet à la classe des problèmes NP-complets.

Encore une fois, la conséquence de ces recherches est un renforcement du pessimisme engendré par Gödel, la plupart des problèmes que l'on sait résoudre sont infaisables, c'est-à-dire qu'ils ne peuvent être résolus en temps polynomial.

Les dernières recherches dans ce domaine montrent une issue à ces résultats définitivement négatifs. Il faut redéfinir la notion de démonstration ou de preuve. Au sens de Hilbert, une preuve est une séquence de symboles régie par des règles strictes partant d'axiomes pour induire de nouveaux résultats. Cependant, il est communément admis qu'un théorème n'est vrai que si aucun mathématicien n'est en mesure de prouver le contraire !

C'est cette idée qui peut servir au développement d'une nouvelle conception des démonstrations. Un outil de communication qui sert à convaincre qu'un énoncé est juste. Cette idée a déjà été exploitée pour la recherche des grands nombres premiers. Il est en effet extrêmement difficile de déterminer si un nombre est premier ou non quand le nombre de chiffres de ce nombre devient important, par conséquent on se contente de tests dit de pseudo-primalité qui permettent de montrer qu'un nombre \(n\) a une probabilité fixée d'être premier. Dire qu'un nombre \(n\) a une probabilité de \(-10^{-30}\) d'être premier n'exclut pas la possibilité que ce nombre ne soit pas premier, il ne s'agit évidemment pas d'une preuve au sens strict du terme. Cependant, on peut aisément rétorquer aux puristes détracteurs de cette nouvelle conception d'une démonstration, qu'il est nettement moins périlleux de faire confiance à un pseudo-premier de Rabbin-Miller qu'en une démonstration formelle d'une centaine de pages d'un théorème difficile !

Un résultat très impressionnant issu de ces recherches montre qu'une large classe de problèmes dont la démonstration est polynomialement longue peuvent être vérifiés avec une très haute probabilité de succès (si on a codé la démonstration dans le système adéquat) en tirant aléatoirement certains caractères de la démonstration !