Versione classicaVersione mobile
OpenEdition Books

L’algorithmique et les sciences

 | 
Bernard Chazelle

L’algorithmique et les sciences

Leçon inaugurale prononcée le jeudi 18 octobre 2012

Bernard Chazelle

Nota dell’editore

La chaire d’Informatique et sciences numériques du Collège de France reçoit le soutien de l’Institut national de recherche en informatique et en automatique (Inria).

Pour un affichage optimal de la version HTML, nous vous recommandons d'utiliser le navigateur Mozilla Firefox.

Testo integrale

1Monsieur l’Administrateur,
Mes chers Collègues,
Chers amis,

Introduction

2On rapporte du grand physicien danois, Niels Bohr, cette anecdote peut-être apocryphe :

— Professeur Bohr, je vois que vous avez un fer à cheval accroché au mur. Ne me dites pas que vous croyez à ce genre de choses !
— Rassurez-vous, je n’y crois pas du tout, mais on m’a dit que ça marche même quand on n’y croit pas.

3Ainsi en va-t-il de la révolution algorithmique. Au delà du scepticisme ou de l’engouement du jour pour la dernière nouveauté informatique se cache un de ces changements de paradigme chers à Kuhn. Outil conceptuel subversif, l’algorithme ouvre la possibilité d’un regard nouveau sur les sciences et les technologies qui s’étend bien au delà de ses applications pratiques. Ce cours se propose d’expliquer les éléments constitutifs de cette révolution intellectuelle en marche.

4Certains déploreront une ferveur messianique qui se prête mal à l’esprit critique du Collège de France. Ils s’inquièteront que cette « révolution algorithmique » ne soit moins une invitation à la réflexion qu’à la complaisance béate. On a connu la révolution de la lessive qui lave plus blanc. Va-t-on connaître celle de l’algorithme qui calcule plus vite ? Pour répondre à cette question avec le sérieux qu’elle mérite, il convient d’abord de s’entendre sur le sens des mots. L’algorithme doit son nom à Abū ‘Abdallāh Muhammad ibn Mūsā al-Khwārizmī, fer de lance de la renaissance abbasside à Bagdad au ixe siècle : un pedigree épris de zèle révolutionnaire. Sic transit gloria mundi... Demandez au passant de la rue de vous définir le mot algorithme et sa réponse sera moins évocatrice du Grand Soir que de l’Interminable Jour de Classe. Un algorithme, vous dira-t-il, c’est cette formule péniblement apprise sur les bancs de l’école qui vous permet de multiplier deux nombres sur un bout de papier en alignant des chiffres en rang d’oignons. « Et dire que des gens vouent leur vie à ce genre de choses », ajoutera-t-il avec compassion. Tout le monde sait additionner, soustraire et multiplier, ce qui fait grimper le nombre d’algorithmes universellement connus à trois – ou à quatre, si l’on compte les rares rescapés de l’ère numérique qui savent encore diviser.

5Un algorithme est une séquence d’instructions à suivre minutieusement pour arriver au résultat voulu par une série d’étapes simples et ennuyeuses. Ces instructions se conjuguent souvent au conditionnel : « L’addition est-elle supérieure à 9 ? Si oui, il serait judicieux de faire une retenue. » Les boucles y sont fréquentes : « Continuez d’ajouter les chiffres de la colonne un par un tant qu’il en reste. » Ne vous laissez pas intimider par votre calculette, toute infaillible soit-elle. Elle ne connaît pas plus l’arithmétique qu’un cheval à Longchamp ne connaît le PMU. Ses algorithmes lisent, écrivent et effacent sans comprendre quoi que ce soit.

6La recette de cuisine est la métaphore classique, heureuse mais imparfaite. La cuisine en effet demande un coup de main, un concept étranger à l’algorithme, pour lequel seule compte l’aptitude à l’obéissance aveugle. De fait, si l’art de la cuisine pouvait se réduire au livre de cuisine, il n’y aurait plus de restaurants à trois étoiles mais que des recettes à trois étoiles. Le calcul, lui, doit ses étoiles à l’algorithme qui le pilote, ainsi bien sûr qu’à la fameuse loi de Moore qui prédit le doublement de la puissance des ordinateurs tous les deux ans, et à l’évolution des interfaces.

La complexité algorithmique

7Un algorithme se définit indépendamment de la taille des données. Multiplier des nombres de 10 ou de 10 milliards de chiffres suit non seulement le même principe mais le même mode d’emploi mot-à-mot. Seul le temps d’exécution diffère. La multiplication de deux nombres de 10 chiffres produit une grille de 10 rangées de 10 ou 11 chiffres chacune, et requiert un nombre d’étapes élémentaires au plus proportionnel à 10×11. En général, multiplier deux nombres de n chiffres chacun nécessite un nombre d’étapes au plus proportionnel à n(n+1)≈n2 : on dit alors que la complexité de l’algorithme est de l’ordre de n2. Que le nombre d’étapes soit égal à n2, 3n2, ou 17n2+n n’importe guère : seul compte l’ordre de grandeur, n2. On n’ignore pas ces facteurs constants par paresse mais, au contraire, par un sens aigu des priorités. Ceux-ci souvent reflètent, en effet, des détails de mise en œuvre extrinsèques à l’algorithme en question (tels que la base numérique pour la multiplication). Une autre raison de s’en débarrasser est de rendre à César ce qui est à César. Si votre calculette multiplie si vite, est-ce le fait d’un algorithme hors pair ou d’un processeur turbochargé ? En règle générale, les facteurs constants sont attribuables à la puissance de l’ordinateur et les ordres de grandeur (tels que n2) à la complexité de l’algorithme.

  • 1 Fürer M., « Faster integer multiplication », SIAM Journal on Computing, 2009, no 39, p. 979-1005.
  • 2 Ailon N. et Chazelle B., « The fast Johnson-Lindenstrauss transform and approximate nearest neighbo (...)

8La multiplication d’école est d’une complexité d’ordre n2. Peut-on faire mieux ? La réponse, affirmative, est à même de surprendre. Un algorithme de Schönhage et Strassen atteint une complexité d’ordre légèrement supérieur à n (pour être précis, d’ordre n log n log log n). Il est utile en pratique pour la factorisation des grands entiers. La méthode, améliorée récemment par Martin Fürer1, est basée sur un algorithme attribuable à Gauss, redécouvert par Cooley and Tukey dans les années soixante, et connu sous le nom de transformée de Fourier rapide (Fast Fourier Transform ou FFT). Aussi étrange que cela puisse paraître, le même algorithme qui vous permet d’écouter de la musique et d’interpréter vos examens de IRMf va vous aider à multiplier des grands nombres très vite. La FFT est le plus polyvalent des algorithmes. En collaboration avec Nir Ailon, un de mes anciens doctorants, j’ai montré comment randomiser la FFT pour exploiter le principe d’incertitude, un concept central en mécanique quantique, et faire de la recherche de voisins en très haute dimension2.

9Le reste de cette leçon pourrait faire l’inventaire des algorithmes qui, peut-être à votre insu, ont changé votre vie. Ce serait une belle histoire, une histoire que vous devrez chercher ailleurs. Mon ambition est plus élevée. Elle est de vous convaincre que l’algorithme n’est pas tant un objet utile, tel qu’une voiture, un parapluie, ou un cure-dents, qu’une façon différente de penser.

Et Turing arriva à Princeton

10L’ordinateur est une des rares inventions (comme le laser) dont la théorie a précédé la réalisation. Alors que, pour l’essentiel, l’ingénierie est une série de pratiques théorisées – on a construit des ponts bien avant de comprendre la mécanique – , l’informatique est une théorie mise en pratique. Ainsi son histoire a-t-elle une valeur instructive particulière.

11Les ordinateurs sont d’une diversité inouïe : on en trouve des lents et des rapides, des gros et des petits, des noirs et des gris. Cette diversité est une illusion : tous les ordinateurs sont fondamentalement identiques. Pour saisir cette idée simple mais profonde, remontons soixante-seize ans en arrière, à Princeton, dans le New Jersey. Dans l’ancien Fine Hall, où se côtoient quotidiennement Einstein, Gödel et von Neumann, le jeune doctorant Alan Turing explique son concept de calcul universel à son professeur de thèse, Alonzo Church. L’idée est diaboliquement simple. Supposons qu’on veuille multiplier 27 par 45. Le calcul doit se concevoir, raconte Turing, comme un train se déplaçant sur une voie ferrée infiniment longue. La voie est divisée en cases de longueur égale à celle du train. On commence par écrire les données sur la voie, un chiffre par case :

12La puce ● au milieu indique la séparation entre les données. C’est là que le train démarre. Il est équipé d’un petit cerveau mécanique, un automate, construit pour exécuter un algorithme de multiplication. De même qu’un interrupteur a deux états (ouvert ou éteint), un automate a un nombre fini d’états possibles. Il est décrit par une liste d’instructions couvrant tous les cas possibles, du style :

Si le train est dans l’état 3, sur une case indiquant le chiffre 5, alors il le remplace par le chiffre 7, il se déplace d’une case à droite, et il passe à l’état 8.

13Bien sûr, le déplacement peut aller aussi à gauche. Le choix des symboles est sans importance : nous avons utilisé ●, 0, 1, …, 9 mais 0 et 1 suffisent. On vérifie facilement que le nombre d’instructions, c’est-à-dire la taille de l’automate, est égal à 11 fois le nombre d’états. Cette machine de Turing doit s’arrêter au bout d’un temps fini et laisser la voie dans cet état :

indiquant ainsi que 27×45=1215.

14À force de produire avec succès les listes d’instructions correspondant à ses opérations préférées, Turing finira par se convaincre que tout ce qui est calculable l’est sur une machine de Turing. Cette thèse de Church-Turing, comme on l’appelle aujourd’hui, n’a rien de tautologique. Turing ne définit pas là ce qui est calculable : il lance une gageure. Il défie la postérité de calculer quoi que ce soit que, lui, Alan Turing, ne peut pas calculer avec son petit train. De l’architecture de von Neumann au calcul quantique, en passant par l’informatique en nuage, tout n’a fait que confirmer cette thèse. La limitation principale de la machine de Turing est de ne pouvoir lire et se déplacer qu’une seule case à la fois. En pratique, c’est un handicap rédhibitoire. En théorie, cela n’a pas la moindre importance – du moins semble-t-il.

15Que vient faire Alonzo là-dedans ? Le professeur Church est un personnage : il commence chaque cours en épongeant son tableau méticuleusement, puis il s’assoit et attend, dans un silence religieux, que tout sèche. La dernière molécule d’eau évaporée, il se lève, sort ses notes, et les copie au tableau mot-à-mot. Avec de tels talents pédagogiques, rien d’étonnant donc que sa liste d’étudiants se lise comme un Who’s Who de l’informatique (Scott, Rabin, Rogers, Kleene, Rosser, etc.).

  • 3 Berry G., Penser, modéliser, et maîtriser le calcul informatique, Collège de France / Fayard, coll. (...)

16Turing parle. Church l’écoute avec attention mais n’exprime aucune surprise. Il se trouve qu’il a tracé indépendamment un chemin parallèle, plus abstrait mais équivalent à celui de Turing, le λ-calcul, un des joyaux de la science logicielle3. Turing a plutôt un esprit d’ingénieur, Church de logicien. Leurs parcours séparés, qui se croisent en 1936, feront du premier le père de l’informatique et du second le père des langages de programmation. Tous les deux ont vite saisi l’importance de l’universalité.

Universalité

  • 4 L’idée fut anticipée par Charles Babbage au xixe siècle.

17Au lieu de fabriquer un automate différent pour chaque fonction (addition, soustraction, multiplication, etc.), ne peut-on pas en construire un seul, universel, qui sache interpréter tous les autres ? Après tout, ces automates sont tous décrits par une liste d’instructions. Mais une liste, c’est un texte, une suite de caractères. Écrivons-la sur la voie ferrée et appelons cela un programme. Au lieu de construire un multiplicateur, il suffira alors de construire un automate qui sache lire les instructions de la multiplication et les exécuter. C’est la différence entre savoir cuisiner et savoir lire un livre de cuisine et suivre ses règles. Church et Turing l’ont bien compris : en informatique, cette différence n’existe pas. Il existe une machine de Turing universelle, capable d’effectuer tout calcul, quel qu’il soit4. Pour l’utiliser, on écrit le programme idoine sur la voie ferrée, en faisant quand même attention de bien séparer les données du programme pour ne pas dérouter notre automate universel. On arrive au schéma de calcul suivant :

  • 5 Avec deux symboles, quinze états suffisent. Avec quatre, six suffisent.

L’automate universel a une tâche simple, voire simpliste. Il doit amener le train sur la partie « programme » de la voie ferrée pour interpréter les instructions et faire des aller-retours, utilisant la partie non utilisée de la voie ferrée comme brouillon. Ceci pourrait suggérer une grande sophistication pour cet automate universel, qui doit lire, interpréter, exécuter, etc. Il n’en est rien. C’est une curiosité mathématique que le coucou que vous avez rapporté de votre dernier voyage en Suisse est techniquement plus sophistiqué que l’automate universel de Turing5.

Dualité

18En 1936, Turing et Church ont assimilé l’œuvre de leur collègue Kurt Gödel et, notamment, le concept fondamental de dualité entre programme et données, une notion qui renvoie à la distinction entre signifié et signifiant chère à Saussure. Considérons la machine universelle de Turing programmée de la façon suivante :

Suivant notre convention, le programme est à gauche et les données à droite. La commande est donc d’effacer les données, c’est-à-dire le mot Répéter, ce qui donne :

Supposons qu’on change de convention et qu’on décide que le programme soit à droite :

19La machine répète alors le mot Effacer sur la voie ferrée, ce qui donne toute autre chose :

Un martien qui atterrit sans connaître cette convention ne peut pas prédire ce qui va se passer. Ce problème n’existait pas avant notre adoption de la machine universelle. Personne, en effet, ne va confondre un cerveau féru de multiplication avec des nombres à multiplier. Par contre, traiter à la fois le programme et les données comme un texte crée une dualité entre programme et données, qui apparaissent ainsi comme les deux revers de la même médaille. Il est difficile de croire que nous touchons là à une des idées les plus fécondes du siècle dernier. Et pourtant...

Autoréférence

20Amusons-nous un peu. Puisque que, par dualité, le même texte peut être interprété soit comme programme soit comme données, essayons ce schéma :

Le programme ordonne la double impression des données. Ceci, bien sûr, sous-entend la disponibilité d’une imprimante, qui va donc sortir :

  • 6 Les esprits tatillons observeront qu’il manque les caractères du milieu : |●|. Remplaçons donc la p (...)

La voie ferrée s’est autoreproduite ! Soulignons l’importance des mots « deux fois », sans lesquels il n’y a pas d’autoreproduction6. On retrouve ici le schéma des virus informatiques et, conceptuellement, de la réplication de l’ADN. Les gènes sont les données (le signifiant) et les protéines qu’ils codent sont les programmes (le signifié). La dualité entre gènes et protéines permet à la nature de distinguer deux fonctions : l’une, syntaxique, d’arrangements de symboles (le codage des gènes) et l’autre, sémantique, de processus biochimiques remplissant des fonctions préprogrammées (les protéines). Bien sûr, les systèmes autoreproducteurs vivants posent des problèmes autrement plus complexes que les virus informatiques, mais la notion de dualité entre programmes et données n’en reste pas moins fondamentale en biologie. En particulier, elle ouvre la voie à une approche algorithmique de ces processus plus riche et plus expressive qu’un traitement purement informationnel.

21Il est probable que c’est de Gödel que Church et Turing ont appris à mesurer la puissance expressive du concept d’autoréférence. Qu’a fait, au juste, cet Autrichien de génie ? On pourrait mentionner sa preuve de l’existence de Dieu, un argument ontologique en logique modale digne de Saint Anselme, mais ayant déjà prêté à l’algorithme des prétentions révolutionnaires, ne lui rajoutons pas des vertus théologiques. Hilbert avait émis l’hypothèse qu’il serait peut-être possible de démontrer en séries d’étapes finies toutes les vérités mathématiques : son fameux Entscheidungsproblem (indécidabilité). Celles-ci étant souvent de nature infinie, la question est de savoir, en somme, si le fini peut « dompter » l’infini. Par exemple, il est bien connu que l’ensemble des nombres premiers n’est pas borné. Voici une proposition qui concerne un ensemble infini, mais qu’on sait prouver en un nombre fini d’étapes logiques élémentaires. En est-il de même de tous les théorèmes mathématiques ? Naturellement, il faut s’entendre sur les règles du jeu. On s’accorde donc sur un langage qui permette d’écrire des théorèmes et de rédiger des démonstrations : on appelle cela une axiomatique.

22Question : Est-ce que tout théorème a une preuve dans une axiomatique donnée ? En 1931, Gödel prouve que si celle-ci permet de définir les nombres entiers, alors la réponse est négative. Sa démonstration magistrale a deux volets. Le premier affirme que toute axiomatique calculable, cohérente, et suffisamment riche pour faire de l’arithmétique contient des propositions vraies qui sont indémontrables à l’intérieur de ce système. Le second, un corollaire immédiat, nous assure qu’aucun système du type précédent ne peut démontrer sa propre cohérence.

  • 7 La valeur métaphorique de l’indécidabilité est, par contre, indéniable. Il est clair que l’autoréfé (...)

23Les théorèmes d’incomplétude de Gödel ont longtemps exercé une telle séduction sur les esprits qu’on en a souvent oublié leurs limites d’usage. D’abord, le système doit être formel. Jacques Bouveresse s’est insurgé à juste titre contre l’usage de l’indécidabilité dans des systèmes qu’on ne sait pas formaliser7. Ensuite, l’axiomatique doit être finie (ou du moins calculable) – sinon rien de plus simple que de garantir la complétude en promouvant comme axiome tout théorème indémontrable – et suffisamment riche pour pouvoir faire de l’arithmétique. Ce dernier point semble un détail mais ne l’est pas : par exemple, tous les théorèmes de géométrie classique sont démontrables.

24Imaginez-vous être le rédacteur en chef d’un journal dont la mission est de publier toutes les vérités. On vous accorde l’éternité, vous déniant ainsi l’excuse d’avoir manqué de temps. Allez-vous publier cette dépêche ? « Cette phrase ne sera jamais publiée. » Si vous le faites, la prédiction s’avère alors fausse et vous publiez une ineptie. Si vous ne le faites pas, elle est donc vraie et vous privez vos lecteurs d’une vérité. Conclusion : votre journal peut être cohérent ou complet mais pas les deux à la fois. Il en va de même de toute axiomatique calculable de l’arithmétique. Résumons. Le concept de dualité nous offre l’option d’interpréter le texte « Cette phrase ne sera jamais publiée » comme une prédiction ou comme une simple suite de symboles. Le concept d’autoréférence nous permet de faire de cette suite de symboles l’objet même de la prédiction, ce qui conduit à l’incohérence ou à l’incomplétude. Les théorèmes de Gödel sont profonds mais simples. L’usage de la machine de Turing nous permet de les prouver en quelques lignes.

25Cette tension entre l’élégance formelle du monde de Church et le pragmatisme ingénieur de celui de Turing se lit dans toute l’histoire des langages de programmation (cf. le contraste entre Lisp et Fortran ou entre ML et C). Ouvrons, à cette occasion, une petite parenthèse philosophique. Dans l’univers de Church, tout est interprétation. Mais n’est-ce pas une activité fondamentalement circulaire ? Pour interpréter, il faut une règle d’interprétation. Mais pour interpréter cette règle, ne faut-il pas d’autres règles, et ainsi de suite à l’infini ? Cette question, soulevée par Wittgenstein dans le contexte de l’impossibilité du langage privé, et reprise en termes algorithmiques par Kripke, se dissout naturellement dans le monde de Turing, où la physique évite la régression à l’infini. Au bout du compte, la machine de Turing est faite d’atomes soumis aux lois de la physique, et la physique, elle, n’interprète pas ses propres lois : à l’inverse, ce sont les lois qui l’interprètent. Le petit train de Turing tranche le nœud wittgensteinien.

26Il faut rappeler que l’autoréférence n’est pas l’apanage de l’informatique : George Bernard Shaw nous a bien conseillé de ne pas suivre les conseils des autres ; Groucho Marx nous a dit son refus d’appartenir à tout club qui accepterait des gens comme lui. Yogi Berra nous a parlé de ce restaurant auquel plus personne n’allait car la file d’attente était trop longue. Et puis il y a la fameuse pipe de Magritte, adaptée ici aux besoins de cette leçon inaugurale.

Figure 1

Figure 1

D’après Magritte.

27L’autoréférence confère aux algorithmes leur puissance en leur donnant accès à la récursivité et au point fixe. Comme je l’ai déjà évoqué, c’est la forme syntaxique qui permet au fini d’exprimer l’infini. Le moteur de recherche de Google, PageRank, est un mode d’emploi fini pour un objet (la Toile) quasiment infini. Soit, mais quelle est la pertinence de l’indécidabilité dans un monde informatique forcément fini ? Dans une lettre écrite à un von Neumann souffrant, Gödel se demande si l’indécidabilité des mathématiques serait un obstacle à l’automatisation des preuves. Il observe qu’il est possible de programmer une machine de Turing universelle afin qu’elle nous dise si, oui ou non, il existe une démonstration de taille au plus n d’un théorème donné. Toutes les preuves connues étant de taille finie, ce programme nous permet, a priori, de démontrer en pratique tout théorème prouvable – à moins, bien sûr, que cela prenne un temps fou. Si l’on dénote par f(n) le nombre d’étapes de la machine, l’optimisme est de rigueur tant que f(n) suit une croissance polynomiale (de l’ordre de nc pour une constante c). Si, par contre, f(n) suit une croissance exponentielle du genre 2n, le projet est voué à l’échec. Gödel esquisse là un analogue fini de l’indécidabilité. Sa lettre anticipe d’une décennie la notion de complexité algorithmique.

28Nous sommes en mars 1956. Einstein est mort l’année précédente et von Neumann succombe d’un cancer quelques mois plus tard. Rentré en Angleterre en 1938, Turing rejoint quelques mois plus tard l’équipe de Bletchley Park pour décrypter, avec succès, le code militaire nazi et jouer ainsi un rôle décisif dans la victoire de la bataille de l’Atlantique. En 1952, il est arrêté pour homosexualité et condamné à une castration chimique. Deux ans plus tard, Alan Turing se suicide. En 2009, le premier ministre britannique, Gordon Brown, lui présente des excuses posthumes.

Peut-on automatiser la créativité ?

29La complexité du calcul se définit par les ressources qu’il requiert, notamment le temps (la durée maximale du voyage ferroviaire pour un problème de taille donnée) et la mémoire (le kilométrage de voie ferrée utilisé par le train). On définit la classe P des problèmes que l’on peut résoudre en temps polynomial, c’est-à-dire au moyen d’un algorithme de complexité d’ordre nc, où n est la taille du problème et c est une constante. On y trouve la multiplication, le tri, la transformée de Fourier, le test de primalité, la cryptographie à clé publique, les moteurs de recherche, etc. La classe P est naturelle pour diverses raisons. Elle inclut tous les problèmes qu’un ordinateur devrait pouvoir résoudre en pratique (tant que c n’est pas trop grand). Elle est invariante sous composition : un calcul reste polynomial si chaque étape y est remplacée par un autre calcul polynomial, une procédure très courante en construction d’algorithmes.

30La complexité polynomiale se caractérise par le fait qu’un doublement de la taille des entrées se traduit par un accroissement de la complexité d’un facteur constant. C’est ce qu’on appelle une loi de puissance, un concept bien connu des physiciens pour sa caractérisation du phénomène d’invariance d’échelle. L’idée est qu’à une constante près un changement fixe d’échelle sur la taille des entrées n’a pas d’effet sur la complexité d’un algorithme polynomial. N’est-ce pas le cas de tous les algorithmes ? Non. L’algorithme qui consiste à multiplier 27 par 45 en ajoutant 27 à lui-même 45 fois n’est pas polynomial mais de complexité d’ordre 10n (où n est le nombre de chiffres du multiplicateur).

31Ceci conduit à définir une autre classe, EXP, regroupant tous les problèmes qu’on peut résoudre en temps au plus exponentiel, c’est-à-dire 2nc, pour tout c constant. Non seulement cette classe contient P mais l’inclusion est stricte. Si P est sans aucun doute premier au hit-parade de la complexité, EXP n’est pas deuxième. Cet honneur revient à NP, la classe nondéterministe polynomiale, qui, dès les années soixante, a reçu l’attention de Cook, Levin, Karp, et de certains cryptologues. Un problème appartient à NP si vous pouvez vérifier en temps polynomial toute solution qu’on vous propose. Il est évident que NP contient P. Déterminer si les deux classes sont identiques est un des grands défis scientifiques de notre époque, une question dont l’issue a le potentiel de révolutionner notre société. Avant d’expliquer pourquoi, revenons à la distinction entre polynomial et exponentiel. Est-elle bien justifiée ? Après tout, une complexité exponentielle d’ordre 1.00001n n’est-elle pas préférable à une complexité polynomiale d’ordre n100 ?

  • 8 Un propos à tempérer par la possibilité, aussi improbable soit-elle, que les ordinateurs quantiques (...)

32La maturité d’une science se lit dans son ontologie. En physique, la centralité des concepts d’énergie, de force, de masse, et de température semble évidente, mais l’est-elle vraiment ? N’oublions pas qu’avant d’être jetés aux oubliettes, le phlogistique, la force vitale et le calorique furent jadis des piliers incontournables de la science. L’invariance d’échelle en complexité, que l’on appelle polynomialité, est au cœur de l’ontologie informatique. En cryptographie, nul ne « connaît » une information qui n’est pas accessible en temps polynomial, même si elle l’est en temps exponentiel (comme par exemple une clé de déchiffrement RSA). En mathématiques, nul ne « connaît » le plus petit nombre premier à n chiffres (pour une grande valeur de n), car les seules méthodes disponibles pour le calculer sont exponentielles. Remarquons au passage que ce mur de feu entre polynomial et exponentiel est le même qui donne son sens à la deuxième loi de la thermodynamique, celle qui vous assure que faire réchauffer votre café ne va pas le transformer en glaçon. La classe P correspond aux problèmes dont le calcul reste borné par une mesure invariante d’échelle : elle est la réponse au Entscheidungsproblem de Hilbert dans le monde physique8.

  • 9 Pour une excellente introduction aux classes de complexité, cf. Arora S. et Barak B., Computational (...)

33Revenons à NP. Vous êtes en charge d’un grand dîner. De combien de tables avez-vous besoin ? Par souci de convivialité, vous préféreriez en utiliser le moins possible, mais voilà, on vous a fourni une liste de paires d’ennemis jurés (Christophe,Gertrude), (Paul,Claire), (Carole,Jeanne)... à ne pas asseoir à la même table coûte que coûte. Question : Trois tables suffisent-elles ? Le problème appartient à NP puisqu’il est facile de vérifier qu’un placement hypothétique des invités autour de trois tables respecte toutes les interdictions. Peut-on trouver ces assignations en temps polynomial ? (Exercice : Montrer comment en trouver une, si elle existe, en temps exponentiel.) Le lecteur aura bien sûr remarqué l’asymétrie de la classe NP : s’il m’est facile de vous convaincre que trois tables suffisent, comment dois-je m’y prendre pour vous convaincre qu’il en faut au moins quatre le cas échéant ? Prouver le possible semble plus facile que prouver l’impossible : la seule preuve qui vient à l’esprit est d’énumérer tous les placements à trois tables, et de vérifier qu’aucun d’entre eux ne marche – une opération extrêmement coûteuse. Résumons : P et NP expriment respectivement ce qu’on peut prouver et ce qu’on peut vérifier en temps polynomial9.

  • 10 Ce problème s’appelle 3-coloriage de graphes dans la littérature scientifique.

34Le problème des trois tables est complet pour la classe NP. Cela signifie qu’un algorithme pour le résoudre en temps polynomial peut en faire de même pour tout problème dans NP. L’équivalent médical serait une maladie universelle : si vous savez la traiter, alors vous savez aussi soigner toutes les autres maladies ! Le problème des trois tables est-il le seul NP-complet10 ? Pas vraiment. On en connaît des milliers. Le parfum d’universalité qui s’en dégage reflète l’expressivité fantastique de NP. Savoir placer ses invités autour de trois tables implique de savoir casser la cryptographie à clé publique et réduire à néant tout le commerce électronique, de savoir replier des protéines et reconstruire des arbres phylogénétiques, de savoir gagner au Sudoku et prouver les grandes conjectures mathématiques. Un seul obstacle : personne ne sait comment résoudre le problème des trois tables en temps polynomial...

35Il est important de cerner les limites de l’universalité dans NP. La plus sérieuse est l’accent mis sur le pire cas. Certains problèmes sont faciles à résoudre : par exemple, si les paires ennemies sont des couples de sexe différent, deux tables suffisent évidemment. D’autres exemples seront par contre très difficiles. Peut-on le savoir à l’avance ? Bâtir une théorie de la NP-complétude qui capture la difficulté en moyenne, une nécessité en cryptographie, s’est avéré une tâche ardue. On perd en effet la propriété d’invariance sous composition que nous offre une théorie basée sur le pire cas. On ne sait pas non plus ce que constitue un modèle de complexité statistique réaliste. Prenons l’exemple classique du repliement des protéines. La transformation d’une chaîne linéaire d’acides aminés en sa structure tridimensionnelle caractéristique est un problème d’optimisation NP-complet. Vraiment ? On a dû oublier d’en avertir la nature, qui semble n’avoir aucun problème à la résoudre en quelques milliers de secondes ! La sélection naturelle semble avoir éliminé du monde vivant les polypeptides incapables de minimiser leur énergie libre instantanément. Je reviendrai sur les problèmes de complexité du monde vivant.

36Concluons sur une note psychologique cette introduction au mystère de P et NP. Les spécialistes misent sur leur inégalité. Pourquoi ? Il y a beaucoup de raisons, dont aucune n’est très convaincante. L’argument anthropomorphique rejette l’égalité P=NP comme un affront à notre humanité. Si prouver n’est pas plus difficile que vérifier, alors créer une œuvre d’art n’est pas plus difficile que de l’apprécier. Bach n’a pas plus de mérite à composer ses cantates que j’en ai, moi, à les savourer. Vous avez aimé Flaubert ? Mes félicitations, vous êtes aussi méritant que le grand écrivain. Métaphores saugrenues ? Peut-être, mais quitte à spéculer, autant le faire de façon métaphoriquement saugrenue.

Pile ou face

37La plupart des grandes découvertes récentes en complexité algorithmique ont mis en valeur le rôle unique joué par l’aléa, la troisième grande ressource algorithmique après le temps et l’espace. Les non-initiés auraient tort de ne pas être surpris. Bien sûr, l’aléa est au cœur des sondages d’opinion et des protocoles cliniques en médecine, donc son utilité en informatique ne devrait faire aucun doute. Mais curieusement, l’aléa est indispensable là où on l’imagine accessoire et inutile là où on le juge nécessaire !

  • 11 C’est-à-dire en utilisant des circuits sans se soucier du temps requis pour les concevoir.
  • 12 Impagliazzo R. et Wigderson A., « P=BPP unless E has subexponential circuits : derandomizing the XO (...)

38Clarifions une confusion possible. Des méthodes de Monte Carlo par chaîne de Markov au moteur de recherche de Google, l’aléa est indispensable en pratique. Soit, mais quel est l’interêt théorique de décorer nos algorithmes d’instructions du genre : « Pile ou face ? Si pile, faire A ; sinon faire B » ? L’aléa confère-t-il au calcul un avantage superpolynomial ? Peu d’experts y croient. La raison en est que l’existence même de problèmes dans NP qu’on ne peut pas résoudre en temps sous-exponentiel (non-uniformément11) nous donne la possibilité de simuler l’aléa de façon déterministe en temps polynomial12. Autrement dit, les deux propositions suivantes sont incompatibles : (i) l’aléa est utile pour NP ; (ii) les problèmes NP-complets sont vraiment difficiles. À faire un prognostic, on rejette (i) et on parie sur (ii), confiant que, dans le cadre de NP, les nombres aléatoires ne servent à rien !

  • 13 Chazelle B., The Discrepancy Method: Randomness and Complexity, Cambridge University Press, 2000.

39Curieusement, bien qu’accessoire comme ressource de calcul, la randomisation est un outil conceptuel indispensable. Elle est aux algorithmes ce que la visualisation est à la géométrie. L’imagination la réclame, et on ne compte plus le nombre d’algorithmes optimaux découverts d’abord sous forme probabiliste pour être plus tard dérandomisés, c’est-à-dire débarrassés de tout vestige d’aléa. C’est par ce biais que j’ai découvert la construction optimale des enveloppes convexes en dimension fixe13. Bien que cet algorithme n’ait aucunement besoin d’aléa, il semble impossible de vraiment le comprendre sans y avoir recours, tant les fonctions utilisées deviennent alors d’apparence magique. Les années quatre-vingt-dix furent une grande période de dérandomisation en algorithmique.

  • 14 Agrawal M., Kayal N. et Saxena N., « PRIMES is in P », Annals of Mathematics, 2004, no 160, p. 781- (...)

40Un exemple classique concerne la primalité. L’ensemble des nombres premiers a beau être infini, le plus grand connu à ce jour ne contient que quelques dizaines de millions de chiffres. De toute évidence, le test élémentaire est ici voué à l’échec : « Diviser N par k=2,3,…,√N ». Cet algorithme est exponentiel dans la taille des entrées, qui est ici de l’ordre de log N, le nombre de bits nécessaires à la représentation de N. Durant plusieurs décennies, les seuls algorithmes polynomiaux pour tester la primalité étaient probabilistes. Il y a une dizaine d’années, Agrawal, Kayal, et Saxena prouvèrent que l’aléa n’est, en fait, pas nécessaire, et qu’on peut tester si un nombre N est premier en temps polynomial en log N sans faire usage de nombres aléatoires14.

41Il reste des exemples notoires de problèmes pour lesquels les seuls algorithmes polynomiaux connus sont probabilistes et leur dérandomisation nous échappe : (i) factoriser un polynôme à plusieurs variables sur un grand corps fini ; (ii) générer un nombre premier entre N et 2N ; (iii) approximer le volume d’un polyèdre en haute dimension à un facteur constant près. Concluons cette introduction à la randomisation en mentionnant une application toute simple sur laquelle je retournerai bientôt : les projections aléatoires.

  • 15 La nécessité de partager les bits aléatoires rend cette solution peu utile en pratique. Par contre, (...)

42Imaginons une situation où vous et moi tenons à nous assurer que nos versions respectives de Hamlet sont strictement identiques. Peut-on le faire sans devoir échanger l’intégralité du texte ? Une fois assurés que les deux tailles coïncident, voici comment un simple envoi de 10 bits suffit à nous convaincre de l’identité des deux textes avec un risque d’erreur inférieur à un sur mille. D’abord, nous nous entendons sur une source commune de bits aléatoires, r1r2r3… La version de Hamlet sur mon portable consiste également en une longue suite de bits h1h2h3… Je vais compter le nombre d’indices i tels que hi = ri = 1 et je vous envoie un bit indiquant sa parité : par exemple, 0 si le nombre est pair et 1 s’il est impair. Je répète cette opération dix fois de suite, en utilisant des bits aléatoires différents à chaque fois. La communication consiste donc en dix bits. De toute évidence, ces bits coïncideront avec les vôtres (calculés de la même manière) si nos versions de Hamlet sont identiques15. Si elles ne le sont pas, la probabilité d’une coïncidence est égale à 2–10, ce qui représente moins d’une chance sur mille. Notez le fait crucial que le risque d’erreur ne dépend ni de la taille du document ni du nombre de bits divergents.

Que sais-je ?

43Le Collège de France a une riche tradition en philosophie de la connaissance. Il est donc bien naturel d’évoquer ici les ramifications épistémologiques de l’aléa algorithmique. L’informatique nous confronte de façon concrète et brutale à un certain nombre de questions philosophiques classiques : l’identité, par exemple. Un dessin fameux du New Yorker fait dire à un chien devant son écran d’ordinateur : « Sur Internet, personne ne sait que tu es un chien. » Comment prouvez-vous en ligne que vous êtes qui vous êtes ?

44Pour certains, est connaissance toute croyance vraie et justifiée. L’idée remonte à Platon, alimente le rejet de la métaphysique par le Cercle de Vienne, et se retrouve au cœur des débats en philosophie analytique dans les pays de langue anglaise. La justification de la croyance est là pour disqualifier la connaissance fortuite. Je crois fermement que cet ouvrage a un destin de best-seller. Avoir raison rend cette croyance vraie mais ne lui confère en rien le statut de connaissance, car je serais bien en mal de la justifier. Il est midi, ma montre m’indique qu’il est midi. Voici donc une croyance vraie justifiée. Mais voilà, ma montre est en panne ! Certains philosophes n’y voient pas là une connaissance. Soit, la justification n’est peut-être pas suffisante mais elle est certainement nécessaire. Toute justification, bien sûr, doit être vérifiable, mais vérifier peut être long et ardu. Pensez à la classification des groupes simples finis, une preuve de mathématiques longue de plusieurs milliers de pages. Un des grands résultats de l’informatique théorique des vingt dernières années affirme que l’aléa algorithmique rend la vérification triviale. Rien, à mon avis, n’illustre la puissance conceptuelle des algorithmes mieux que cette conclusion profondément contre-intuitive. C’est l’affaire du PCP. Avant de l’aborder, parlons de la persuasion à divulgation nulle, une question épistémologique cruciale en cryptographie.

45Me voici P-DG de la société Dînez-en-Paix International qui, pour une prestation relativement onéreuse, vous indiquera s’il est possible de placer vos invités autour des trois tables. M’attendant à un certain scepticisme de votre part – après tout, c’est un problème NP-complet – je vous propose une formule « appât » bon marché. Pour une somme modique, je vais vous convaincre que je connais la réponse à votre question, mais sans laisser transparaître la moindre information à son sujet. Nous sommes confrontés ici à une question d’épistémologie algorithmique. La solution réside dans les preuves interactives.

46Voici ma stratégie. Je compile une liste indiquant le numéro de table de chaque invité. Vous piochez une paire interdite au hasard et vous me demandez de vous révéler les deux numéros de table correspondants. S’ils sont identiques, de toute évidence, je vous ai menti, et vous partez en claquant la porte. Sinon, vous recommencez ce petit jeu plusieurs fois. Au bout d’un certain temps, si vous êtes toujours là, votre assurance que j’ai dit la vérité approche de 100 % – car s’il y a une paire identique, vous finirez bien par tomber dessus. De mon côté, je fais bien attention de renuméroter les tables à chaque fois en faisant une permutation aléatoire de {1,2,3}. Pour éviter toute supercherie de ma part, je vous montre la liste avec tous les numéros cachés derrière un voile, et je révèle, devant vous, les numéros de la paire que vous avez demandée. De cette façon, je ne peux pas tricher en changeant lesdits numéros après votre requête.

  • 16 Par exemple, révéler une suite de pile-ou-face aléatoire ne peut constituer une divulgation d’infor (...)

47Cet algorithme est à divulgation nulle dans la mesure où il ne vous révèle qu’un seul bit d’information, en l’occurrence, si oui ou non, trois tables suffisent. Toutes les autres informations ne sont que des paires d’entiers distincts piochés au hasard dans {1,2,3}. Nul ne peut apprendre à quelqu’un ce qu’il connaît déjà. On emploie ici la version probabiliste de ce principe et on déclare nulle toute connaissance statistique que tout un chacun sait produire soi-même en temps polynomial16.

  • 17 Goldreich O., Micali S. et Wigderson A., « Proofs that yield nothing but their validity or all lang (...)

48Votre problème de tables n’est pas un cas isolé. Je peux vous convaincre que je sais résoudre un puzzle ou une grille de sudoku sans rien vous révéler de leurs solutions. Plus généralement, toute question dans NP (entre autres) admet un protocole à divulgation nulle – du moins si l’on suppose l’existence de « fonctions à sens unique », un concept clé en cryptographie17. Si P=NP, bien sûr, tout ceci n’a pas grand intérêt, car vous êtes alors en mesure de résoudre vous-même votre problème sans passer par mes services.

49Revenons à l’asymétrie de NP. Supposons que trois tables ne suffisent pas. Comme on l’a vu, la stratégie esquissée plus haut finira par révéler une erreur (avec forte probabilité). N’est-ce pas un signe que quel que soit le statut du problème, à savoir si trois tables suffisent ou pas, le protocole nous le révèlera ? Non. La réussite de tous les tests vous donne une quasi-conviction que je connais la réponse. Un échec ne vous apprend rien d’autre que ma supercherie. Je peux vous convaincre que le problème est résoluble mais pas qu’il ne l’est pas. C’est ici que le concept d’honnêteté trouve son utilité en épistémologie algorithmique. Après tout, si vous me faisiez confiance, pourquoi s’embêter avec ce protocole de listes voilées ? Il suffirait alors que je dise : « Je sais faire. » En 1962, quand Dean Acheson offrit à de Gaulle des preuves photographiques de la présence de missiles nucléaires soviétiques à Cuba, ce dernier refusa, ajoutant : « La parole du président des États-Unis me suffit. » Naturellement l’enjeu pour vous, un dîner qui tourne mal, est autrement plus sérieux qu’une guerre nucléaire, et ma parole, bien entendu, ne saurait vous suffire.

50Il existe des protocoles de dialogue à divulgation nulle pour décider, par exemple, qui de deux personnes est la plus âgée. Le protocole, malheureusement bien plus compliqué que le précédent, se déroule en une suite de questions-réponses au bout de laquelle chacun sait qui est le plus âgé sans toutefois avoir la moindre information supplémentaire sur l’âge de l’autre. En pratique, la divulgation nulle est utile pour l’authentification : puis-je vous convaincre que je connais un mot de passe sans vous le révéler ? (Peut-être êtes-vous un imposteur.) La genèse cryptographique de ces développements s’explique par le besoin de concevoir des protocoles d’échanges où toute fraude est impossible. Être malhonnête n’a de sens que si ça paye. Dans un univers où toute tricherie est détectée, l’honnêteté, étant plus facile à vivre que la malhonnêteté, devient le seul comportement rationnel. La preuve à divulgation nulle fait écho à la fameuse exhortation de Hilbert, « Nous devons savoir. Nous saurons », à laquelle il rajoute une pointe d’ironie : « Et nous ne saurons pourquoi. »

La magie du PCP

  • 18 Toute autre proposition mathématique servirait aussi bien d’exemple.

51Les années quatre-vingt-dix ont vu s’effectuer une refonte complète de la classe NP, s’achevant en point d’orgue avec l’identité NP=PCP (log n, 1). Le point de départ est une révision du concept même de preuve. Je me réveille un beau matin avec, en tête, la démonstration complète de l’hypothèse de Riemann, une conjecture profonde touchant au comportement aléatoire des nombres premiers18. Par anticipation d’une gloire certaine, je saute du lit et tape fébrilement sur mon portable les 500 pages de ma preuve. Ceci fait, je poste sur la Toile cette dépêche historique : « Riemann vaincu ! » Soudain, le doute me saisit. Est-ce bien sage d’infliger à la communauté mathématique le plein impact de mon génie ? Qui va se porter volontaire pour lire mon chef-d’œuvre ? Vous, bien sûr. Seulement voilà : vous ne m’accordez que 10 secondes. Aucun problème. Voici ce que je fais :

    • 19 Le PCP, à ne pas confondre avec la PCP, qui est illégale, est l’acronyme de Probabilistically Check (...)

    Étape 1 : Je traduis ma démonstration dans le langage PCP19. Cette traduction, purement syntaxique, ne requiert aucune compétence mathématique. Elle suit des règles fixes, accessibles sur la Toile et indépendantes de la démonstration.

  • Étape 2 : Vous piochez dans ma traduction et vous en extrayez une dizaine de bits pris plus ou moins au hasard sans en regarder aucun autre. Vous les soumettez à quelques tests, eux-aussi disponibles sur la Toile. Selon les réponses que vous obtenez, en quelques secondes, vous déclarez mon annonce vraie ou fausse. Le risque d’erreur est infime.

  • 20 La preuve est une formule booléenne (ainsi que la valeur des variables qui la satisfont), exprimant (...)
  • 21 Ceci contredit-il le doute régnant sur la nécessité de l’aléa pour le calcul polynomial ? Non. L’éc (...)

La seule façon de ne pas être choqué par ce tour de passe-passe est de le connaître déjà ou de ne pas le comprendre. Passons en revue ses éléments essentiels. Premièrement, la traduction reste de taille polynomiale par rapport à l’original20. Deuxièmement, à l’étape 2, vous ne faites pas de déclaration sur ma preuve mais sur mon annonce. Si vous l’acceptez, c’est que l’hypothèse de Riemann est correcte : il se peut alors que ma preuve soit quand même fausse mais, dans ce cas-là, il est facile de la corriger. Votre rejet, par contre, signifie que ma preuve est une imposture (mais certainement pas que l’hypothèse de Riemann est fausse). Notez que je peux utiliser l’étape 2 moi-même pour m’assurer que ma propre preuve est correcte. Troisièmement, l’algorithme étant randomisé, il y a un petit risque d’erreur, qui décroît exponentiellement vers 0 avec le nombre de bits lus. Encore plus étonnant peut-être est que de ne lire que trois bits pris au hasard dans la preuve donne déjà une confiance quasi absolue si la preuve est correcte et de 50 % si elle fausse. Le hasard joue un rôle essentiel : pas d’aléa, pas de PCP21.

52L’algorithme PCP s’étend à toute la classe NP. (À la différence de la divulgation nulle, aucune hypothèse cryptographique n’est nécessaire.) Par exemple, l’entreprise Dînez-en-Paix International peut vous convaincre, en quelques mots, que trois tables suffisent pour asseoir vos invités si c’est possible. On note la distinction avec les preuves interactives à divulgation nulle, où c’est vous qui essayez de vérifier mon assertion et moi qui oppose une résistance par souci de ne dévoiler aucune information supplémentaire. Le PCP renverse les rôles. Mon but est maintenant de vous convaincre et, pour cela, je suis prêt à abattre toutes mes cartes. La seule restriction, c’est votre impatience.

« Bon, on essaie le PCP ? »

53Pensez aux écoliers à qui l’on rabâche que toute démonstration de maths est à la merci de la moindre faute. Le PCP dit qu’il n’en est rien – ou plutôt que toute preuve peut être réécrite de telle façon qu’être largement correct devient identique à l’être complètement. L’intuition culinaire est limpide : une preuve est un sandwich et une erreur est un soupçon de confiture qu’on essaie d’étaler uniformément sur son pain pour le rendre plus savoureux. Si ma preuve est impeccable, enfin à part cette malheureuse égalité 1+1=3 en page 317, le PCP va se charger de répandre cette bourde un peu partout pour qu’un échantillonnage aléatoire de quelques mots suffise à l’attraper. L’idée est séduisante mais se heurte à plusieurs difficultés. D’abord, se répandre pour accroître sa visibilité n’a de sens que si tout le monde ne fait pas de même. Dois-je donc propager toutes les fautes, s’il y en aablealementrj41 de Riemann est correcte : il se peut aloth"textlè le rendre plus savoureux. Si ma preuve est impeccable, enfin à part cette malheureuse égass="texte">Étape 1 : Je traduisntuvabord, ymples s Le hvoilà,lassiqueivulgatia m> sanmologiquue un r nyenne,vous convlosophnre re mchangesquue un rlgatia bassurermpe, clune question épisavec fl devons savoir. Nous saurons©chantillonnage alsitions arbres unt le seus quel en mones afAorriger. l les fapour lomial chantillonnage alclass=e façon qu’être large dialogue à divulgation nulle pour décider, par exemonte 7, j êtes  que l n’n sûdes nombres premiersLe 161Prn21">(..bassurst séa Toiliv ctif vous finirespan>L n’n que trour m’assurer que ma ptcalcul reifica un puzzPythala ethropomorphunNP.sseupondblèmes bord,zzo R

Acquista

Versione a stampa

Caricamento in corso

Unavailable