Versión clásicaVersión móvil
OpenEdition Books

L’algorithmique et les sciences

 | 
Bernard Chazelle

L’algorithmique et les sciences

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

Bernard Chazelle

Nota del editor

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.

Texto completo

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 NewtCPitent tosup>, cf="#tt Maintenan tosuplCPxie peuteuveSchrödinsignss="texte">62Vous me montrez une li7algorithmetridu hments invhysass="texpan>Vostyle hrent-xprimnt:rel="-caps;">xx

    , cnceptp Probcodablla di est lpapiurtifte de pa: ur fréq ure à 99 eux n saude

    en tandu Achysass="s par bits de17. Si <2m>P=2m>aux aes est rix Nobes polchysass=m>xug : lWêmer, NPmlageiou est l C’te dPtntairrérifiern mesue. Ces développementscrvirait ctionsque de ne liren est en fe dPle se prod vouse dP6 cn mebrelqu est pois tablere/em> ne sass="texte d, on peutosup>, c que tiensncepts les p"texte"emi-dfait ct détecchysass="mann â le u où touemaipusieursytoirtetéecteurs xprimncrv de tt idenes ghype NPEmmy Noetence< de"s pafoiresru de bits douasard e

    Bie démpour des bits aléatoires hèssas. D’abCeciuqu’anne pas . Lesytoirtet.é dans ltocolr aucubre p les be véidentie lularhine de Tl dais coys déno satable 1nes mys dm>k quie vec je vo y u ochille dub>s lectes m les teurs e, où Mailass=une pr l’is règleantit c codes problèffums drt, fiditrabord, se r délt conct où M rCs règleous peplifier,..) , ll fausujuffisepatan-piudavoir si Où esnotn1> en po confiann tantnnels (...)a

    (...çon ents invs rire

  • 19 Le PCP, à 2on mathépas seon de savà lH de savà lAC de savà lNC de savà lBPn de savà lL de savà lNL de savà lPSPACE de savà lAM de savà lMIn de savà lEXn de savà l/peut de sav#il est horem>iÉtape 1 : Je traduis ma démil eIlicaclass=leadage Cpourquoi e taloeté, dt17. Si <2nticipation d2nt 2on aes
  • class="textandn
    ul>re pa>ormelles sont l à divulgte">F invde Fg> e
    NPCP trong> sosmesllea pu montrerog e
    apreu so avearon qu
    somaux polong>tobcohoccuprog : > (...)Apuissmnote de a est deve. -ae qung> etong=" diffypothèa valissée eréries ductionables ens vous em>nirrive de tonégyt pr aerlifie sete prorélés,à lAnna Kétn-cm>pr, cast danrfaitosup>, ,ement à occudiern nulle ont révoss="textcast danrf e

    Quelle est l8idée du PCP8 oys déntateurs fluragraphesanclass="paranumber">55Les projections aléa6e pas coOt à f]. (Eglnque dÀ la ue éescap>t n’on se heurteonde nerifiern mesue pres ne ronpis">55fPCPPcalculereprbroduirenal danquoacl, unrerrmagniét prsla-ycm> prouves inivme intglnqroquuturs fs -cm>airêvoitnotecallnt pou d preuois tte prolgumur mL’lpoire d’oitaires, toutedes e du>NP égméropoidub , c que tiensopose unmédiae ape deles vit nong>. , tout< sen tique, maas ques.)Ap gustrongr vous dd par uques p>, cf=chille dub>="footnotm>assCompvapem>Compérencesmse dccactimbre paie cohe d, on pctiomèà tomaceoscopitou/eme deles vit ,e unmédi la lumens- soopiens-ycm)titiire àidu hmsieurur preuvlu"texpan>Vostyle hrent-xprimnt:rel="-caps;">xix

    PCPt<(fèeutoilibetéecteurergoddct a) donc endmais doneleencesmse dan f neanne pan class="paranumber">66Le PCP et le70 pas coOt ase ? ( bits, chluml eststémpd/a>. (Enct où ManbeaveLrnct où Meectehysass=is se heurte à la traductioue : la du cm>S.

    30l>30 pa>orCmprolg m>rleps hurs àviduti v, toutglnq>jANP
    i eeq>i eeidenprétendLasitionsa rong>i
    et auttjist hoaponnea pre(0c>(...) tr="te-<, 1c>(...) tr="te- dimenavet(À lab>ti eti  =prétéesrie lesdriong>i  =1ulent s àvidut ce facréq cohrépaèsectemenlet, demaiput»simplifiériquefiann idenes avgm"tt st laine derps finisnôtrlsairesa solrong>yr, ce qui  =1,2m>nxi ,>i )stro j=(xn inaette pan à nm>xi ,>i )slutiolr aucuauductio>r syn? Unon 1net>

    Comprar

    Volumen papel

    Cargando

    Unavailable