Version classiqueVersion mobile

L’algorithmique et les sciences

 | 
Bernard Chazelle

L’algorithmique et les sciences

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

Bernard Chazelle

Note de l’éditeur

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.

Texte intégral

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 a beaucoup ? Ceci soulève un problème encore plus sérieux. Puisque la traduction dans le langage PCP est ma propre responsabilité, pourquoi irais-je la saupoudrer d’idioties en supplément de celles qui y sont déjà ? Parce que c’est la règle et que la confiance règne ? Bien sûr que non. Le manque de confiance est la base de travail du PCP. Comme la preuve à divulgation nulle, le PCP est avant tout un détecteur de mensonges. Alors que le sens commun nous dit que la confiance facilite la persuasion, le PCP prouve qu’il n’en est rien.

54Si je ne sais pas démontrer l’hypothèse de Riemann, ma « preuve » n’est qu’une suite d’étapes conçues, sciemment ou pas, pour vous induire en erreur. Votre but est de vous rendre compte du subterfuge. D’accord, mais comment allez-vous vous assurer sur la base d’un regard furtif que j’ai bien démontré l’hypothèse de Riemann et pas le théorème de Pythagore ? Il y a un parfum d’absurdité dans l’air.

Quelle est l’idée du PCP ?

55Les projections aléatoires vous permettent de vérifier, en un nombre constant d’échanges, que nos versions de Hamlet coïncident avec un risque d’erreur infime. Plus abstraitement, vous pouvez vérifier que je détiens une vérité que vous-même possédez. Le PCP pousse le défi plus loin. Il vous permet de vérifier quasi-instantanément une vérité que je prétends avoir mais que, vous, ne possédez pas. Pour donner un sens à cette affirmation, on suppose que cette vérité est une preuve formelle écrite dans un langage dont vous connaissez les règles. Bien sûr, rien ne m’oblige à suivre ces règles. C’est à vous de savoir si je triche. On peut avoir du PCP une intuition logique ou algébrique. On aborde ces deux modes intuitifs, l’un après l’autre.

La logique du PCP

56La traduction dans le langage PCP consiste à rajouter à ma preuve originale toutes ses conséquences logiques. Une démonstration est une suite cohérente de théorèmes, de lemmes, et d’observations. Rajoutons-y tous les corollaires qui en découlent – ou plutôt une collection de taille polynomiale « représentative » du tout. On se pose alors deux questions : (i) a-t-on là une preuve de quelque chose ? (ii) si oui, de quoi ? Il se trouve qu’en testant quelques étapes prises au hasard, on peut vite s’assurer que la preuve n’est pas un long tissu d’inepties. En particulier, on peut vérifier que 90 % des étapes sont cohérentes. Si c’est le cas, alors un miracle se produit. On peut, sans effort, faire grimper cette probabilité à 100 %. Comment ?

57Gavée de redondance, la preuve PCP offre une floraison de chemins logiques. Alors qu’une preuve traditionnelle offre une seule voie conduisant de A à B, la preuve PCP en propose une telle pléthore que, même entachée de 10 % d’erreurs, il est non seulement possible, mais facile, de choisir un chemin correct de A à B. Par analogie, le fait que 10 % des rues soient bloquées dans Paris ne devrait pas vous empêcher de vous rendre du Pont de Sèvres à la Porte des Lilas. Dans le format PCP, aussi contre-intuitif que cela puisse paraître, une preuve correcte à 90 % mérite les égards dus à une preuve parfaitement correcte. En particulier, on peut en prendre des bribes au hasard et corriger instantanément toute faute qui s’y trouve.

58Étant maintenant assuré que ma preuve PCP est logiquement cohérente, ou du moins peut être traitée en tant que telle, vous devez vérifier que c’est bien l’hypothèse de Riemann qu’elle démontre. Le scénario-cauchemar est le suivant : j’ai établi correctement un théorème différent, mais dont l’énoncé est quasiment identique à celui de l’hypothèse de Riemann. Comment s’armer contre une telle éventualité ? Il s’avère que nous sommes déjà parés. En vertu d’une propriété aussi simple que puissante, tirer toutes les conséquences d’un résultat amplifie ses différences avec tout autre, même un quasi-identique. (Le lecteur familier des codes correcteurs ne sera pas surpris.) Un regard rapide sur la preuve PCP révèlera alors toute différence suspecte.

59Il est utile d’éclaircir un point. Où est passée la chronologie de la preuve ? Une démonstration est une chaîne linéaire d’implications logiques. Tel un fleuve qui coule, elle progresse d’étape en étape et ne peut donc être lue que dans le « sens du courant ». Cette intuition est profondément fausse. Toute preuve mathématique formelle peut être lue et vérifiée dans n’importe quel ordre (par exemple, en marche arrière) de la même façon que la validité d’un calcul d’une machine de Turing peut être testée dans un ordre arbitraire. La raison tient à un des concepts les plus fondamentaux de l’informatique : la localité du calcul.

60Toute étape d’une preuve ou d’un calcul n’implique que la lecture d’un état et d’un petit nombre de caractères : tant que chaque étape a accès à l’information dont elle a besoin, leur ordre n’a aucune importance. Pourquoi ceci prête-t-il souvent à confusion ? Parce que ce n’est pas le cas des maths qu’on pratique. Les démonstrations qu’on trouve dans les ouvrages scientifiques ne sont pas des preuves mais des séries de conseils et d’indices pour aider les lecteurs à trouver la démonstration eux-mêmes. Ceci explique leur brièveté et leur fréquente difficulté. Par contraste, les preuves formelles sont longues, faciles à vérifier, et humainement impossibles à comprendre. Le PCP est le rêve d’un comité de rédaction : toute soumission peut être vérifiée immédiatement et sans effort.

L’algèbre du PCP

  • 22 Le lecteur allergique à tout raisonnement mathématique, mais qui curieusement se retrouve ici, est (...)
  • 23 Avec deux tables, la question est dans P et donc, a priori, d’une pertinence douteuse pour les preu (...)

61Pour les affamés de démonstrations que ces maigres explications n’auraient pas rassasiés, voici du ravitaillement. Le PCP inaugure une théorie de ce qu’on pourrait appeler les « codes correcteurs fonctionnels22 ». Du fait que vérifier une preuve mathématique peut s’exprimer dans le langage de NP, l’hypothèse de Riemann se réduit au problème des trois tables. La transformation est loin d’être évidente mais l’intuition est claire : vérifier une preuve est assimilable à un calcul de machine de Turing de temps polynomial dans la taille de la preuve en question, donc exprimable par tout problème NP-complet, notamment celui des trois tables. Pour simplifier, réduisons le nombre de tables permises à deux23. Un exemple pour rafraîchir les esprits : deux tables suffisent pour accommoder la liste de paires ennemies (Paul,Claire),(Paul,Jeanne) mais pas la liste (Paul,Claire),(Claire,Jeanne), (Jeanne,Paul).

  • 24 Il est facile de voir qu’il existe toujours une solution respectant au moins la moitié des interdic (...)

62Vous me montrez une liste L de paires ennemies et, après un moment de réflexion, je vous annonce savoir asseoir les invités autour de deux tables numérotées 0 et 1. J’affirme ainsi ma (prétendue) connaissance d’un vecteur t=(t1, …, tn) de n bits indiquant le numéro de table ti de chaque invité i et garantissant que, pour chaque paire ennemie (i,j) de L, la somme ti + tj est égale à 1 (puisque les seules solutions acceptables sont 01 et 10). Mon rôle est de vous convaincre que je dis bien la vérité. Le protocole doit être quasiment instantané, donc il n’est pas question de vous faire lire le vecteur t dans sa totalité. Bien sûr, si ma « solution » est truffée de paires non-résolues (i.e., ti + tj ≠ 1), alors piocher dedans au hasard plusieurs fois vous révèlera rapidement la supercherie. Que faire si ce n’est pas le cas, notamment s’il n’y a qu’une ou deux paires ennemies non-résolues ? Avec |L|=109, c’est chercher une aiguille dans une botte de foin24. Pour cette raison, je traduis ma « preuve » t dans le langage PCP. Voici les règles de traduction. Définissons la fonction

ft(x)=t1x1+…+tnxn

pour tout vecteur x=(x1,…,xn) de n bits. Toutes les opérations sont faites dorénavant modulo 2, ce qui consiste à remplacer tout nombre pair par 0 et tout nombre impair par 1. La preuve PCP n’est rien d’autre qu’une énumération exhaustive de toutes les valeurs de ft(x). On en fait une table F et on désigne le bit correspondant à ft(x) par F[x]. (Exercice : Expliquer pourquoi interpréter x=(x1,…,xn) comme un nombre en base 2 fournit la position de ft(x) dans la table F.) Si ma solution t est correcte, je n’ai aucune raison de falsifier cette table PCP et, de fait, je m’assure que F[x]=ft(x) pour tout x.

Exemple : On numérote Paul, Claire, et Jeanne 1,2,3 dans cet ordre et on fixe L=(1,2),(1,3). Ma solution est d’asseoir Claire et Jeanne ensemble à la table 1 et Paul seul à la table 0, d’où t=(0,1,1) et

F=(0, t3, t2, t2 + t3, t1, t1 + t3, t1 + t2, t1 + t2 + t3)
 =(0,1,1,0,0,1,1,0)

63On observera le phénomène d’étalage de confiture : la moindre erreur dans t, par exemple transformer un de ses bits, change F en quatre endroits. Toute erreur se répand sur la moitié du sandwich.

Ce codage effroyablement redondant de t, connu sous le nom de Walsh-Hadamard, est « localement décodable ». C’est cette propriété qui va vous permettre de débusquer toute supercherie de ma part. En effet, si je n’ai pas de solution correcte, il m’est offert deux façons de tricher : la fraude de cohérence est de ne pas se soucier que F dénote les valeurs de pour un vecteur t ; la fraude de validité est de s’en soucier mais de choisir un vecteur t incorrect, c’est-à-dire qui assigne une paire ennemie à la même table.

Fraude de cohérence

Vous choisissez deux vecteurs de n bits au hasard, x et y, et vous vérifiez que F[x+y]=F[x]+F[y], ce qui nécessite une consultation de la table PCP en trois endroits. Ma promesse d’une solution t sous-entend que ma table F liste toutes les valeurs de ft, qui est une fonction linéaire. Autrement dit, vous saurez certainement que j’ai menti si votre test échoue. Vous le répétez plusieurs fois pour faire diminuer le risque d’erreurs, rafraîchissant les vecteurs aléatoires x et y à chaque fois. L’absence d’échec vous fait conclure à l’existence d’un vecteur t tel que la table F diffère des valeurs de ft(x) en moins de 10 % d’endroits : autrement dit, le nombre de vecteurs x tels que F[x]≠ft(x) est inférieur à 2n/10. Un nombre suffisant de répétitions garantit cette propriété avec une probabilité supérieure à 99 %. Ceci se démontre de façon élégante avec la transformée de Fourier. (Tiens, encore elle !) Telle une droite dans l’espace à deux dimensions ou un plan dans l’espace à trois dimensions, la table F représente, à moins de 10 % d’erreurs près, un hyperplan de la forme {(x, ft(x))} dans l’espace {0,1}n+1.

Fraude de validité

64Plus étonnant encore, si aucune fraude de cohérence n’est détectée, vous pouvez alors calculer n’importe quel ft(x) sans connaître t. Bien sûr, consulter F[x] n’est pas fiable puisque jusqu’à 10 % de ses valeurs peuvent être corrompues. Vous prenez donc un vecteur aléatoire y et calculez

F[x+y]–F[y]

  • 25 Vous pouvez amplifier vos chances de succès en répétant plusieurs fois cette procédure, surnommée a (...)

ce qui nécessite la consultation de deux bits dans la table. Bien que corrélés, les vecteurs y et x + y sont chacun parfaitement aléatoires, donc la probabilité que ce calcul ne nous donne pas ft(x+y)–ft(y), autrement dit, par linéarité, ft(x), n’excède pas 20 % (moins de 10 % de chance qu’il y ait un problème à x+y et moins de 10 % qu’il y en ait un à y). La beauté de ce procédé est double : (i) bien que 10 % de la table puisse être corrompue, il vous est possible d’évaluer ce quelle devrait être n’importe où25 ; (ii) cette évaluation ne nécessite pas la connaissance de t (qui requiert n bits, donc est hors de portée). En d’autres termes, vous avez accès à tous les points d’un hyperplan à n dimensions sans jamais le connaître ! Nous sommes proches du dénouement. Vous connaissez l’emplacement dans la table F des sommes ti + tj correspondant aux paires ennemies. Appelons x1,…, xm ces emplacements. Vous devez vous assurer que ft(x1)=…=ft(xm)=1, ce que vous faites avec la méthode des projections aléatoires en testant que

r1ft(x1)+…+rmft(xm)=r1+…+rm (mod 2)

pour des bits aléatoires r1,…, rm. Par linéarité, la somme de gauche n’est autre que ft(r1x1+…+rm+xm), que vous savez évaluer avec une chance de réussite supérieure à 80 %. (Exercice : Pourquoi se contenter de vérifier que le bit de F en position r1x1+…+rm+xm est égal à r1+…+rm modulo 2 n’est pas vraiment une bonne idée.) Si aucun de ces tests ne révèle une anomalie, vous êtes prêt à accepter la validité de mon annonce. Répéter cette procédure plusieurs fois diminue le risque d’erreur exponentiellement.

*

  • 26 Pour un traitement en profondeur, je renvoie le lecteur à Arora S. et Barak B., Computational Compl (...)

Pour des raisons d’expressivité, il nous faut un problème NP-complet, donc on doit adapter notre raisonnement à la version des trois tables si l’on s’intéresse à l’hypothèse de Riemann. Je dois alors rajouter à ma preuve PCP des conditions non-linéaires du genre tk = titj, ce qui ne pose pas de difficultés particulières. Le talon d’Achille de ma preuve PCP est sa taille astronomique. Sa longueur exponentielle, 2n, tient à une redondance excessive. La rendre polynomiale n’est pas chose facile. On passe des fonctions linéaires aux polynômes sur des corps finis dont on varie la caractéristique à loisir pour produire différents parfums de PCP que l’on mélange judicieusement. Les arguments originaux ont été simplifiés au fil des années, notamment par des percées sur les codes localement décodables et les graphes expanseurs26. Pour résumer, tout problème dans NP de taille n qui a une solution admet une preuve de taille polynomiale en n qui peut être vérifiée en un nombre constant d’accès à ladite preuve.

65Une des grandes applications théoriques du PCP concerne les algorithmes d’approximation. Il est NP-complet de savoir si trois tables suffisent. Grâce à la théorie du PCP, on a pu montrer qu’en supposant un analogue probabiliste de l’inégalité P ≠ NP, il est hors de question de savoir si l’on peut se contenter d’un nombre de tables qui diffère de l’optimum par un facteur de n0.999. Le problème des trois tables est réfractaire à toute solution : le PCP nous dit que toute approximation est également sans espoir. Pas besoin, donc, de rechercher des algorithmes hypersophistiqués. Des techniques simples de programmation semi-définie constituent sans doute la solution de choix.

66Le PCP et les algorithmes à divulgation nulle ont révolutionné notre conception mathématique et épistémologique de la preuve. Ces développements invitent toutefois à la sobriété. Le PCP ne s’occupe que des valeurs de vérité des propositions logiques. Les mathématiciens, eux, veulent moins savoir ce qui est vrai que comprendre pourquoi ça l’est. Je viens de vous convaincre que l’hypothèse de Riemann est en fait un théorème. Maintenant vous savez mais vous ne comprenez pas. Sur la question du pourquoi, le PCP se tait, fidèle à l’adage de Wittgenstein : « Sur ce dont on ne peut parler, il faut se taire. »

Les algorithmes naturels

  • 27 On pense bien sûr aux équations de Newton, Maxwell, Boltzmann, Einstein et Schrödinger.

67Le triomphe de la physique du xxe siècle a été en grande partie celui des mathématiques. Il relève du miracle que quelques équations éparpillées sur un bout de papier suffisent à expliquer, avec une précision étourdissante, l’essentiel du monde physique qui nous entoure27. Le prix Nobel de physique, Eugène Wigner, s’émerveillait de « l’efficacité déraisonnable des mathématiques dans les sciences de la nature ». Sans dénier l’intérêt épistémologique de ce propos, il convient de le reformuler. Wigner avait à l’esprit les sciences physiques. En guise de réponse, le mathématicien Israel Gelfand ironisa que la seule chose plus étonnante que l’efficacité des mathématiques en physique, c’est leur inefficacité en biologie. Excès de langage, soit, mais nul n’entretient l’illusion que guérir le cancer ou élucider le cortex cérébral puisse se réduire à la solution de quelques équations différentielles. La raison en est simple. L’univers physique est bâti sur des principes de symétrie et d’invariance – dont les liens s’expriment dans un théorème classique d’Emmy Noether – qui font cruellement défaut en biologie. Si l’on se réfère au schéma :

Biologie = Physique + Histoire,

on se heurte à la dure réalité que l’histoire est le grand briseur de symétrie. Il y a une distance considérable entre la régularité d’horloge du système solaire et les mystères du système immunitaire. Ce n’est pas une question de taille : après tout, le problème à trois corps n’est pas soluble, mais des phases de transition sur particules le sont. Le problème tient à la diversité des facteurs et des modes d’interaction, qui supposent un langage suffisamment expressif pour se prêter à plusieurs niveaux d’abstraction. Ce langage est celui des algorithmes naturels. Avant d’aborder ce sujet de plain-pied, il est utile de clarifier le sens du mot « complexe ». Tel est l’engouement pour la complexité qu’on en distingue quatre parfums :

  • Sémantique. Ce qui est difficile à comprendre : le seul sens du terme pour 99 % de la planète.

  • Épistémologique. Ce qui est difficile à prédire : le temps qu’il fera dans un mois ; le succès en librairie de cet ouvrage. Certains systèmes chaotiques, aussi imprévisibles soient-ils, sont faciles à comprendre. D’autres sont mystérieux.

    • 28 coNP, PH, AC, NC, BPP, L, NL, PSPACE, AM, MIP, EXP, P/poly, #P, pour ne citer que les plus connus.

    Instrumental. Ce qui est difficile à calculer : P, NP, et toute la zoologie de la complexité algorithmique28.

  • Descriptif. Ce qui est difficile à modéliser. L’émerveillement de Wigner tenait à la faible complexité descriptive de la physique. C’est le propre de la symétrie de pouvoir s’énoncer de façon concise. Le langage de la physique est au haïku ce que celui de la biologie est au roman proustien. Pour faire face à cette richesse de langage, l’outil premier est l’abstraction, un concept éminemment informatique et l’approche la plus fructueuse du concept d’émergence.

  • 29 Fisher J., Harel D. et Henzinger T.A., « Biology as reactivity », Communications of the ACM, 2011, (...)

68Si les processus vivants sont pilotés par le « logiciel de la nature », la sélection darwinienne est alors l’optimiseur de code ultime. Avec le nombre et le temps de leur côté (1030 spécimens et des milliards d’années), les bactéries ont eu le loisir d’affûter leurs algorithmes naturels. C’est donc sans surprise que les informaticiens se tournent vers la biologie pour trouver l’inspiration : réseaux neuronaux, calculateurs à ADN, optimisation par colonies de fourmis, etc. Des concepts fondamentaux comme la modularité, la stochasticité, le consensus, la synchronisation, le calcul distribué ou la tolérance aux pannes, sont communs à la biologie et à l’informatique. De fait, des techniques logicielles telles que la théorie des types et le model checking ont été déployées avec succès pour la vérification automatique des propriétés temporelles de certains systèmes biologiques29. Par contraste avec les efforts actuels visant à s’inspirer de la biologie pour inventer des algorithmes nouveaux, en robotique ou ailleurs, ma recherche suit la direction inverse. Elle fait de la nature le champ d’application d’une nouvelle théorie des algorithmes. Tout démarre avec la question suivante : quelle est la pertinence d’une démarche algorithmique dans les sciences de la vie ? En présence d’une masse de données hétérogènes, l’analyse statistique ne suffit-elle pas ? Non. Aussi indispensables soient-elles, les statistiques de vol ne vous éclaireront pas plus sur les nuées d’oiseaux qu’une analyse de fréquence de mots dans Anna Karénine ne nous dévoilera la psychologie du comte Vronski. Une approche algorithmique est indispensable. De même qu’on étudie les équations avec des équations, on doit étudier les algorithmes naturels avec des algorithmes.

Les systèmes d’influence

69On désigne par agent toute entité capable de communiquer, calculer, et agir par le biais d’un algorithme : ce peut être une personne, un oiseau, un insecte, un microbe, un atome, etc. L’idée n’a d’intérêt que dans un contexte collectif : un réseau social, une volée de grues, une construction de termitière, une détection bactérienne de quorum, un réseau de particules magnétiques, etc. La perspective « agent », appelée parfois lagrangienne, n’est pas aussi courante qu’on pourrait l’imaginer. Une approche eulérienne lui est souvent préférée. Par exemple, il ne viendrait à l’esprit de personne de modéliser le climat en traitant chaque molécule d’air comme un agent soumis à des forces newtoniennes. On préfère découper l’espace en petites boîtes fixes (infinitésimales) et suivre, par le biais d’équations différentielles, la pression et la température dans chaque boîte à tout instant. Au lieu de poursuivre des quintillions de particules dans une chasse effrénée à travers l’espace, on étudie l’évolution de quelques distributions : autrement dit, on préfère mettre à jour des cartes météorologiques. En thermodynamique, on réduit la complexité microscopique monstrueuse d’un moteur à vapeur à un résumé succinct consistant en quelques paramètres macroscopiques (température, pression, volume, entropie, etc.). Un des triomphes de la science du xixe siècle a été la découverte des conditions (d’équilibre et d’ergodicité) qui rendent un tel résumé conforme à la réalité.

70On a là un exemple lumineux du concept d’abstraction. Le même phénomène physique peut être modélisé et interprété de deux manières différentes selon l’échelle à laquelle on l’étudie : microscopiquement, c’est le règne de Newton ; macroscopiquement, c’est celui de Carnot, Clausius, et Boltzmann. Le même système dynamique se prête à un traitement mathématique complètement différent selon la proximité à laquelle on l’observe. Le cas n’est pas isolé. Le traitement du mouvement brownien par Einstein et du groupe de renormalisation par Wilson sont deux autres illustrations magistrales de la puissance du concept d’abstraction en physique. L’idée est encore plus fondamentale en informatique. Sans abstraction, les milliards de lignes de code qui constituent la Toile ne seraient qu’un colossal charabia inutilisable.

  • 30 Hegselmann R. et Krause U., « Opinion dynamics and bounded confidence models, analysis, and simulat (...)

71Pour clarifier la discussion, passons à un exemple classique de calcul distribué « naturel » : les systèmes HK (Hegselmann-Krause)30. Ce modèle de dynamique sociale s’intéresse à l’évolution des opinions au sein d’un groupe d’individus. Chaque agent i détient, par exemple, une sensibilité politique exprimée par deux nombres réels xi et yi entre 0 et 1. La valeur de xi signifie la position de l’agent i sur l’échiquier politique (0 pour l’extrême-gauche, 1 pour l’extrême-droite, et toutes les valeurs entre les deux). La valeur de yi indique le libéralisme de l’agent : anarchique si yi =0 et autoritaire si yi =1. Les individus communiquent entre eux suivant un principe « d’influence par affinité » selon lequel on n’est réceptif qu’aux arguments des gens dont les opinions sont similaires aux nôtres. On fixe donc un seuil r > 0 et, à chaque étape t =1,2,…, l’opinion (xi,yi) de l’agent i, interprétée comme un point dans le plan, se déplace vers le centre de gravité de tous les points (xj,yj) à distance au plus r. Les opinions de tous les agents sont mises à jour de manière synchrone et le processus est répété à perpétuité.

Figure 2

Figure 2

Un système HK en action.

72La figure 2 représente l’évolution d’un tel système, avec un trait reliant dans un graphe tous les agents en relation d’influence. Distribuées initialement de façon aléatoire, les opinions perdent vite leur isotropie et brisent leur symétrie pour former des « tentacules » qui finissent par se figer en une collection de points fixes. Quand la communication va dans les deux sens, comme ici, où l’influence entre Pierre et Paul est nécessairement réciproque, on peut montrer que le système converge toujours. L’absence de réciprocité, on le verra bientôt, change tout.

73Pourquoi se limiter à deux nombres par agent et à des critères de communication aussi simples ? Les systèmes dinfluence étendent ce modèle à un très haut niveau d’expressivité. Au lieu de deux coordonnées, on définit létat d’un agent par un point xi =(x1,1,…,xi,d). On y trouvera par exemple la position de l’agent, son âge, sa température, sa tension artérielle, ses préférences alimentaires, ses opinions politiques, etc. On stocke ainsi dans xi toute information sur le passé de l’agent i pertinente pour son avenir : cette façon de résumer tout le passé utile pour l’avenir dans l’état présent est la marque d’un système markovien. Si l’agent est un ordinateur, xi représente alors le contenu de sa mémoire. Chaque agent dispose de son propre algorithme de communication lui permettant de déterminer à tout moment qui est une source d’influence en fonction de l’état actuel de tout le monde. Il a également son algorithme daction, qui lui dit comment mettre à jour son vecteur d’état xi en fonction de l’état actuel de ceux qui l’influencent – et de personne d’autre ! Chaque agent est à même de choisir ses propres algorithmes, tous différents des autres. L’objet de cette description est de porter l’attention sur la haute complexité descriptive d’un système où chaque agent est muni de son propre algorithme. Certains agents peuvent être inertes : imaginez des phéromones ou des signaux chimiotactiques.

Figure 3

Figure 3

Les arcs émanant de chaque agent pointent vers ceux qui l’influencent. Par exemple, seuls le chat et le médecin influencent le chien à t =1. À chaque étape t =1,2,…, les agents se déplacent et les arcs sont mis à jour par le biais des algorithmes d’action et de communication.

  • 31 Chazelle B., « Natural algorithms and influence systems », Communications of the ACM, 2012, vol. 55 (...)

74Pour le lecteur en mal de formalisme, un système dinfluence est un système dynamique à temps discret défini par deux fonctions f et G31. D’une part, x ∈ (ℝd)n ↦ f(x) ∈ (ℝd)n, où n représente le nombre d’agents, d est la dimension de l’espace ambiant (d =2 dans fig. 3) et chaque xi de x=(x1,…,xn)∈(ℝd)n encode la position de l’agent i dans ℝd. D’autre part, à tout x correspond un graphe orienté G(x), muni d’un sommet par agent et donc plongé dans ℝd. La fonction-coordonnée fi de f =(f1, …, fn) prend comme entrées les voisins émanant de l’agent i dans G(x) ainsi que leurs positions, et calcule la nouvelle position fi(x) de l’agent i dans ℝd.

75La distinction entre algorithmes d’action f et de communication G reflète notre désir de séparer le syntaxique (qui parle à qui) du sémantique (qui fait quoi). Bien qu’on soit libre de réaliser f et G par des algorithmes déterministes ou randomisés arbitraires, il est dans l’esprit du modèle d’imaginer des agents cognitivement limités, de sorte que les phénomènes émergents soient attribuables plus à la communication collective qu’à la puissance cognitive des individus. Il est bien établi que les insectes sociaux, tels que les termites, les fourmis et les abeilles, accomplissent des tâches d’une sophistication bien supérieure à leurs capacités individuelles.

76Les systèmes d’influence sont capables de modéliser les réseaux sociaux dynamiques, les communautés d’insectes, les oscillateurs couplés, les bancs de poissons, la circulation automobile, les mouvements de foule, les circuits cellulaires, les réseaux protéiques, les transmissions de rumeurs, les épidémies, la polarisation politique, la dynamique des populations, le modèle d’Ising ou encore les réseaux neuronaux ou bayésiens. Une limitation apparente est le nombre fixe d’agents, mais il est facile d’y remédier – une nécessité pour les modèles de croissance de plantes. En examinant de plus près deux cas particuliers de systèmes d’influence, nous évaluerons le mérite d’une approche algorithmique de ces questions, notamment au travers des concepts fondamentaux de preuve algorithmique et de renormalisation.

Les nuées d’oiseaux

  • 32 Voir la vidéo : www.youtube.com/watch?v=XH-groCeKbE
  • 33 Chazelle B., « The convergence of bird flocking », 2009, arXiv:0905.4241v1. Version préliminaire pa (...)

77Chaque soir, au dessus des marais d’Otmoor, près d’Oxford en Angleterre, une volée de plus d’une centaine de milliers d’étourneaux se prête à une chorégraphie à couper le souffle32. Pendant plusieurs minutes, ces oiseaux se livrent à un ballet aérien de haute voltige, fait de spirales drapées s’entrecoupant telles des guirlandes en papier de soie. Aucune collision n’a jamais été enregistrée. Qu’explique cette virtuosité ? Des travaux récents laissent à penser que dans une nuée d’étourneaux – on appelle cela une murmuration – chaque oiseau est influencé par ses quelques voisins les plus proches. Le vecteur d’état de l’oiseau i contient six coordonnées indiquant sa position et sa vélocité. Il faut donc 6n nombres pour décrire à tout moment l’état d’un système de n oiseaux. L’algorithme d’action enjoint le vecteur de vélocité à se transformer à chaque étape par un mécanisme d’alignement, en la moyenne de la vélocité de ses voisins. Après une période de latence, les oiseaux finissent par former des groupes cohésifs qui ne se fragmenteront plus jamais. Dans des cas rares, il est possible que les groupes continuent de fusionner sur une longue durée (fig. 4). Le graphe de communication finit par se figer et la vélocité moyenne de chaque composante connexe devient constante. Les valeurs asymptotiques maximales de ces intervalles de temps sont connues. Comment prouve-t-on ce genre de choses33 ?

Figure 4

Figure 4

L’oiseau au centre du cercle ajuste sa trajectoire pour s’aligner avec celles de ses deux voisins.

78Il est utile de renverser la question et de discuter d’abord de la façon de ne pas prouver un tel résultat. L’approche classique serait de prétendre que le graphe de communication est fixe, de résoudre le système, et puis d’étendre le raisonnement au cas dynamique où les arêtes changent au cours du temps. Expliquons pourquoi cette démarche est vouée à l’échec. Fixer les relations de voisinage une fois pour toutes produit un « oscillateur couplé », un des systèmes les plus étudiés qui soient – pensez aux cellules cardiaques, aux réseaux électriques, aux lucioles, aux failles sismiques, etc. Utiliser les équations du mouvement pour suivre directement la position de chaque oiseau dans l’espace n’est pas forcément chose facile. On contourne cette difficulté en recherchant leurs modes, ce que la théorie des matrices stochastiques nous permet de faire aisément.

79La notion de mode renvoie à la transformée de Fourier mais l’intuition est claire sans recours au jargon technique. Vous faites de la balançoire sur un paquebot en agitant un drapeau à la main. Pour comprendre le mouvement de la grande aiguille de la montre que vous portez au poignet, il est utile de le décomposer en une somme de quatre modes élémentaires. C’est l’approche spectrale. Le mode principal est la vélocité du paquebot, qui à elle seule donne déjà une bonne approximation du mouvement de l’aiguille. On y rajoute le mouvement oscillatoire de la balançoire (le deuxième mode), puis les secousses de votre poignet (le troisième mode), et enfin la rotation de l’aiguille qui tourne (le quatrième mode). On décompose ainsi un mouvement complexe en une somme de quatre mouvements simples et indépendants. Ce dernier point est crucial : en première approximation, le déplacement du bateau n’affecte en rien les aiguilles de la montre qui, elles-mêmes, n’ont pas d’influence sur la balançoire, etc. Ainsi peut-on traiter chaque mode comme si les autres n’existaient pas.

  • 34 Pour des raisons techniques, la masse de chaque oiseau doit être multipliée par son nombre de voisi (...)

80D’une manière similaire, on peut décomposer le mouvement des oiseaux en modes indépendants. Supposons pour simplifier la discussion que le graphe de communication soit connexe. Le mode principal est alors la vélocité du centre de gravité de la collection d’oiseaux34. Il y a toutefois une différence de taille. À part le mode principal, qui reste constant, tous les autres s’atténuent au cours du temps, un peu comme un pendule qui, sans moteur pour maintenir son mouvement, dissiperait son l’énergie (libre) par friction et oscillerait de moins en moins. Intuitivement, les oiseaux essaient de trouver un cap en commun et de s’y rapprocher progressivement. Le gain en consensus se traduit par une perte d’énergie.

  • 35 Chazelle B., « The total s-energy of a multiagent system », SIAM Journal of Control and Optimizatio (...)

81Malheureusement, cette approche « spectrale » échoue lamentablement dès qu’on restaure aux oiseaux leur faculté de changer de voisinage en fonction de leurs positions. Cet échec est brutal : mathématiquement, le coupable est l’absence de bases propres communes pour des matrices qui ne commutent pas. Prosaïquement, il n’y a plus de modes. Que faire ? Mettre sa casquette d’algorithmicien et abandonner l’approche spectrale. (Tâche rude : quand on voit des clous partout, c’est dur de renoncer à son marteau.) On introduit la s-énergie, un paramètre global qui nous informe sur la cohésion de la nuée d’oiseaux35. C’est une série de Dirichlet, un outil puissant en théorie des nombres mais dont l’usage est ici très différent. Pour borner la s-énergie, on suit une approche d’analyse amortie, un domaine issu des structures de données qui n’a a priori aucun rapport avec le système en question. On distribue à chaque oiseau un certain « capital d’argent ». Cette métaphore n’est pas gratuite. L’idée est de mettre en place une économie avec des règles de capital (qui stipulent combien d’argent chaque oiseau doit avoir à tout moment) et des règles d’échange (qui spécifient combien d’argent un oiseau doit passer quand et à qui). Les détails n’importent pas ici. Ce qui compte, c’est d’en saisir le principe sous-jacent : un algorithme naturel de nuées s’analyse par le biais d’un autre algorithme, très différent, d’échanges économiques. En mathématiques, le moyen classique d’étudier une équation est d’en produire une autre. De même, pour comprendre les algorithmes naturels, nos meilleurs outils s’avèrent être d’autres algorithmes.

Figure 5

Figure 5

Le filet de vol. Chaque berlingot représente l’enveloppe convexe des vélocités des voisins de l’oiseau qui lui est associé. Sa vélocité évolue à l’intérieur dudit berlingot, qui lui-même change constamment.

82La s-énergie nous informe sur la cohésion cinétique des oiseaux, c’est-à-dire leur comportement à petite échelle. Pour une vision macroscopique qui nous renseigne, par exemple, sur la possibilité que deux nuées éloignées puissent plus tard fusionner, on fait appel au filet de vol. Quelle en est l’idée ? Faites une vidéo de la murmuration et passez la en marche arrière. Vous pourrez ainsi suivre les relations d’influence en remontant dans le temps. Par exemple, si l’oiseau 1 fait la moyenne des vélocités des oiseaux 4, 7, et 12 au temps t, on regarde de qui les oiseaux 4, 7, et 12 font la moyenne au temps − 1, et ainsi de suite. On représente ça par un arbre dans l’espace-temps à quatre dimensions (fig. 5).

83Pour des raisons techniques sur lesquelles il n’y a pas lieu de s’étendre, la question de savoir si deux nuées sont amenées à fusionner par la suite est réductible à la présence de chemins presque droits dans le filet de vol. Le physicien quantique reconnaîtra dans cette structure un écho des intégrales de chemin : il s’agit d’affirmer (ou d’infirmer) une propriété parmi un nombre exponentiel de chemins possibles. Pour ce faire, on répète la démarche antérieure et on invente un algorithme nouveau. Au lieu de transactions économiques, cette fois-ci, on place une brindille dans le bec d’un oiseau et on lui donne la liberté de la passer à quiconque de ses voisins quand il le désire. Question : Y a-t-il un algorithme de passage de brindille qui la maintient plus ou moins le long d’une ligne droite ? Malgré la possibilité de vol en spirale, la réponse est affirmative. Une fois de plus, on étudie un algorithme par le biais d’un autre. Les preuves ne sont plus algébriques mais algorithmiques, les deux disciplines auxquelles al-Khwārizmī a donné le nom.

Les systèmes d’influence diffusifs

  • 36 On leur permet de calculer toute formule exprimable dans la « théorie du premier ordre des réels ». (...)

84Les systèmes HK mentionnés plus haut sont diffusifs. Le terme indique que la transmission de l’information se fait en prenant des moyennes locales partout, un peu comme l’aspirine passe dans le sang, ou la chaleur se propage le long d’une cuillère qu’on trempe dans l’eau chaude. Une propriété essentielle de ces systèmes est qu’ils se figent dès qu’ils atteignent un consensus : parler à des gens qui pensent comme vous n’est pas de nature à vous faire changer d’avis ; quand toute la cuillère atteint la même température, elle y reste. On dit d’un système d’influence qu’il est diffusif si les algorithmes d’action font évoluer les agents en leur faisant prendre des moyennes (pondérées si l’on préfère) avec leurs voisins. Les algorithmes de communication, eux, restent arbitraires36. (Exercice : Pourquoi l’algorithme de nuées n’est-il pas diffusif ?) Contrairement aux systèmes HK, la communication peut être soit réciproque, soit à sens unique (graphe orienté). Est-il possible de classifier tous les comportements possibles des systèmes d’influence diffusifs en quelques catégories simples et universelles ? La réponse est oui, et la preuve naturellement est algorithmique. Il y a trois types de comportements, dont l’un est extrêmement rare :

  • Convergent. Le système finit par se fixer sur une configuration vers laquelle il se rend progressivement.

  • Asymptotiquement périodique. Après une phase initiale, le système, tel Sisyphe, se met à répéter la même suite de configurations dans le même ordre – ou tend à s’en rapprocher inexorablement. La période du cycle-limite est souvent courte mais peut être exponentielle dans le nombre d’agents.

  • Turing-complet. Le système peut simuler un ordinateur et il est donc impossible, par un théorème classique de Rice, de prévoir toute propriété non-triviale. Étant donné une configuration initiale, savoir où seront les agents dans vingt-quatre heures nécessite d’attendre le lendemain. Le système peut être chaotique (avec une entropie topologique positive), ce qui signifie que prédire les k prochaines étapes nécessite une précision exponentielle en k. Le chaos et l’universalité de Turing requièrent tous les deux un ajustement fin des paramètres.

  • 37 On passe sous silence quelques conditions techniques.

85Comme dans les systèmes de spins en mécanique statistique, la frontière qui sépare l’ordre du désordre, ici le chaos du comportement attracteur (point fixe ou cycle-limite) résulte d’un équilibre extrêmement complexe entre l’entropie et l’énergie, une sorte de match nul entre deux combattants. La frontière critique apparaît sous forme d’ensemble de Cantor dans l’espace des paramètres. Les discontinuités des algorithmes de communication créent un quasi-aléa parmi les changements de voisinage – « quasi » dans la mesure où la dynamique reste entièrement déterministe. Les systèmes d’influence de type diffusif sont presque toujours attracteurs37. De plus, les communications réciproques (téléphone, Facebook, courriel) stabilisent les opinions qui finissent toujours par se figer, alors que celles à sens unique (journaux, radio, télévision) conduisent à la périodicité. Ces résultats théoriques sont en attente de validation expérimentale.

  • 38 Le lecteur intéressé trouvera tous les détails dans : Chazelle B., « The dynamics of influence syst (...)

86Il est surprenant qu’il soit possible de classifier des systèmes d’une telle généralité eu égard à la faculté de chaque agent de communiquer selon des critères arbitrairement complexes qui lui sont propres. L’analyse nécessite un équivalent algorithmique du groupe de renormalisation, un outil essentiel en physique quantique et statistique. L’idée est de traiter récursivement tout sous-système qui s’isole du reste pendant un certain temps. Par exemple, un groupe d’agents n’ayant aucun contact avec le reste de la communauté peut être étudié séparément jusqu’à ce que la communication reprenne. Cela revient à définir des « super-agents » consistant en des sous-graphes induits du réseau de communication. La propagation d’information est alors traitée comme un flot dans des canalisations. Là encore, le traitement est entièrement algorithmique38.

87Deux arguments militent contre la possibilité d’une théorie générale des algorithmes naturels. Le premier est un manque de structure. Mais n’a-t-on pas dit la même chose de la théorie des graphes, un sujet dont les liens avec l’algèbre, la topologie, et plus récemment la géométrie, ont connu un succès retentissant ? Une objection plus sérieuse, c’est qu’avant d’analyser un algorithme naturel, il faut le spécifier. À l’inverse des algorithmes humains, ceux de la nature ne sont pas lisibles à l’œil nu. L’approche ascendante (bottom-up) qui consiste à décrire la fonctionnalité de chaque agent à la main, comme on le fait couramment dans les modèles de vols d’oiseaux, repose sur des arguments de plausibilité parfois ténus. Une approche descendante (top-down) à la fois fonctionnaliste, phénoménologique, et bien sûr statistique, est sans doute incontournable. C’est un sujet aussi ouvert que brûlant.

88The Economist écrivait il y a quelques années que, si Google est une religion, son dieu est sans aucun doute l’algorithme. Il convient d’ajouter à cette observation théologique une note linguistique lourde de conséquence : si les sciences nouvelles se parlent, leur langage est sans aucun doute l’algorithmique. Les algorithmes naturels nous donnent un langage. À nous de le lire, de le déchiffrer, et de s’émerveiller de la littérature de la nature.

Je tiens à remercier Gérard Berry et Emmanuelle Fleury pour leurs utiles commentaires, suggestions et corrections.

Notes

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 neighbors », SIAM Journal on Computing, 2009, no 39, p. 302-322.

3 Berry G., Penser, modéliser, et maîtriser le calcul informatique, Collège de France / Fayard, coll. « Leçons inaugurales », no 208, 2009.

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

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

6 Les esprits tatillons observeront qu’il manque les caractères du milieu : |●|. Remplaçons donc la phrase « Imprimer les données deux fois » par « Imprimer les données deux fois et rajouter |●| la première fois ».

7 La valeur métaphorique de l’indécidabilité est, par contre, indéniable. Il est clair que l’autoréférence permet d’exprimer des contradictions (par exemple, « Je mens ») et que tout n’est pas « accessible » de l’intérieur. Bien qu’imprécises, ces idées sont utiles en dehors du cadre où elles sont énoncées. Je ne suis toutefois pas sûr qu’elles aient besoin de Gödel.

8 Un propos à tempérer par la possibilité, aussi improbable soit-elle, que les ordinateurs quantiques nous permettent de calculer dans NP en temps polynomial (randomisé).

9 Pour une excellente introduction aux classes de complexité, cf. Arora S. et Barak B., Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

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

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 XOR lemma », Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, p. 220-229.

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

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

15 La nécessité de partager les bits aléatoires rend cette solution peu utile en pratique. Par contre, l’idée théorique est, comme on le verra, fructueuse.

16 Par exemple, révéler une suite de pile-ou-face aléatoire ne peut constituer une divulgation d’information car quiconque peut la générer, sinon exactement, du moins avec la même distribution de probabilité.

17 Goldreich O., Micali S. et Wigderson A., « Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems », Journal of the ACM, 1991, no 38, p. 691-729.

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

19 Le PCP, à ne pas confondre avec la PCP, qui est illégale, est l’acronyme de Probabilistically Checkable Proof.

20 La preuve est une formule booléenne (ainsi que la valeur des variables qui la satisfont), exprimant la validité de l’exécution d’une preuve formelle.

21 Ceci contredit-il le doute régnant sur la nécessité de l’aléa pour le calcul polynomial ? Non. L’échantillonnage aléatoire est indispensable aux preuves interactives, qui offrent un modèle épistémologique dont l’accent n’est pas de trouver mais de persuader.

22 Le lecteur allergique à tout raisonnement mathématique, mais qui curieusement se retrouve ici, est invité à passer au chapitre suivant.

23 Avec deux tables, la question est dans P et donc, a priori, d’une pertinence douteuse pour les preuves interactives. Elle reste néammoins parfaitement illustrative du principe de base.

24 Il est facile de voir qu’il existe toujours une solution respectant au moins la moitié des interdictions.

25 Vous pouvez amplifier vos chances de succès en répétant plusieurs fois cette procédure, surnommée autoréductibilité, et en concluant par un vote de majorité.

26 Pour un traitement en profondeur, je renvoie le lecteur à Arora S. et Barak B., Computational Complexity, op. cit.

27 On pense bien sûr aux équations de Newton, Maxwell, Boltzmann, Einstein et Schrödinger.

28 coNP, PH, AC, NC, BPP, L, NL, PSPACE, AM, MIP, EXP, P/poly, #P, pour ne citer que les plus connus.

29 Fisher J., Harel D. et Henzinger T.A., « Biology as reactivity », Communications of the ACM, 2011, no 54, p. 72-82.

30 Hegselmann R. et Krause U., « Opinion dynamics and bounded confidence models, analysis, and simulation », Journal of Artificial Societies and Social Simulation, 2002, vol. 5, no 3.

31 Chazelle B., « Natural algorithms and influence systems », Communications of the ACM, 2012, vol. 55, no 12, p. 101-110.

32 Voir la vidéo : www.youtube.com/watch?v=XH-groCeKbE

33 Chazelle B., « The convergence of bird flocking », 2009, arXiv:0905.4241v1. Version préliminaire parue dans Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 422-431, avec développements ultérieurs dans Proceedings of the 2010 Annual Symposium on Computational Geometry, 2010.

34 Pour des raisons techniques, la masse de chaque oiseau doit être multipliée par son nombre de voisins.

35 Chazelle B., « The total s-energy of a multiagent system », SIAM Journal of Control and Optimization, 2011, no 49, p. 1680-1706.

36 On leur permet de calculer toute formule exprimable dans la « théorie du premier ordre des réels ». Cette théorie est décidable et d’une telle généralité qu’elle inclut à peu près tous les systèmes concevables.

37 On passe sous silence quelques conditions techniques.

38 Le lecteur intéressé trouvera tous les détails dans : Chazelle B., « The dynamics of influence systems », 2012, arXiv:1204.3946v2. Version préliminaire parue dans Proceedings of 53rd IEEE Symposium on Foundations of Computer Science (FOCS), 2012.

Table des illustrations

URL http://books.openedition.org/cdf/docannexe/image/1362/img-1.png
Fichier image/png, 3,1k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-2.png
Fichier image/png, 2,8k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-3.png
Fichier image/png, 13k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-4.png
Fichier image/png, 8,5k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-5.png
Fichier image/png, 5,7k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-6.png
Fichier image/png, 12k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-7.png
Fichier image/png, 7,1k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-8.png
Fichier image/png, 8,7k
URL http://books.openedition.org/cdf/docannexe/image/1362/img-9.png
Fichier image/png, 8,5k
Titre Figure 1
Légende D’après Magritte.
URL http://books.openedition.org/cdf/docannexe/image/1362/img-10.png
Fichier image/png, 69k
Légende « Bon, on essaie le PCP ? »
URL http://books.openedition.org/cdf/docannexe/image/1362/img-11.png
Fichier image/png, 2,2M
Titre Figure 2
Légende Un système HK en action.
URL http://books.openedition.org/cdf/docannexe/image/1362/img-12.png
Fichier image/png, 640k
Titre Figure 3
Légende Les arcs émanant de chaque agent pointent vers ceux qui l’influencent. Par exemple, seuls le chat et le médecin influencent le chien à t =1. À chaque étape t =1,2,…, les agents se déplacent et les arcs sont mis à jour par le biais des algorithmes d’action et de communication.
URL http://books.openedition.org/cdf/docannexe/image/1362/img-13.png
Fichier image/png, 305k
Titre Figure 4
Légende L’oiseau au centre du cercle ajuste sa trajectoire pour s’aligner avec celles de ses deux voisins.
URL http://books.openedition.org/cdf/docannexe/image/1362/img-14.png
Fichier image/png, 675k
Titre Figure 5
Légende Le filet de vol. Chaque berlingot représente l’enveloppe convexe des vélocités des voisins de l’oiseau qui lui est associé. Sa vélocité évolue à l’intérieur dudit berlingot, qui lui-même change constamment.
URL http://books.openedition.org/cdf/docannexe/image/1362/img-15.png
Fichier image/png, 1022k

Auteur

Professeur invité au Collège de France, chaire d’Informatique et sciences numériques (2012-2013)

Le texte et les autres éléments (illustrations, fichiers annexes importés) sont sous Licence OpenEdition Books, sauf mention contraire.

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search