L'informatique théorique : un domaine foisonnant, malgré le blocage persistant de certaines questions fondamentales

Jean-Paul Delahaye, professeur d'Informatique à Lille

L'informatique théorique : un domaine foisonnant, malgré le blocage persistant de certaines questions fondamentales

Depuis deux décennies, l'informatique a connu une évolution rapide qui a suscité une réflexion théorique d'une extrême richesse. Comme à chaque fois en de pareilles circonstances, on s'est aperçu que les mathématiques disponibles non seulement ne répondaient pas à toutes les questions qui se posaient, mais qu'en fait, des domaines mathématiques nouveaux devaient être définis et explorés. Un foisonnement remarquable d'idées et de résultats en est résulté.

En fait, c'est une nouvelle sensibilité mathématique qui est née de l'usage des ordinateurs et des problèmes qu'ils posent à l'esprit théoricien, et si tout remonte à la décennie 1930 avec les travaux de Kurt Gödel, Alan Turing, et Alonso Church sur la calculabilité, dans les dernières décennies, cette sensibilité mathématique nouvelle a connu un essor considérable. À côté des mathématiques du continu, ces mathématiques du discret, du calcul et de l'information se sont épanouies et, on doit constater qu'on est très loin d'avoir parcouru ne serait-ce que les allées principales de ce jardin foisonnant qui croît sur le terreau des circuits électroniques. Tout bouillonne dans cet univers que les mathématiques pures observent maintenant avec grand intérêt.

Organiser des milliards de calculs ?

Donner des ordres précis aux ordinateurs de façon à ce qu'ils fassent ce qu'on attend s'appelle écrire des algorithmes. Les mathématiciens depuis toujours conçoivent de telles procédures de calcul (l'algorithme d'Euclide qui détermine le plus grand commun diviseur de deux nombres est né avec les mathématiques, il y a plus de deux mille ans), mais en pratique la règle implicite était qu'on utilise les algorithmes en opérant à la main quelques dizaines ou au plus quelques centaines d'opérations élémentaires. Lorsque des machines capables de réaliser des millions, puis des milliards de calculs sans erreur furent disponibles, on découvrit que toute une science nouvelle, l'algorithmique, devait se développer et que cette science était d'essence mathématique. Commander des calculateurs automatiques n'est ni simple ni évident et des méthodes au premier regard satisfaisantes peuvent être vaines dans le monde réel des ordinateurs. La résolution de systèmes d'équations linéaires par les formules de Cramer (qui expriment les solutions comme des rapports de deux déterminants) ne vous permettra pas de traiter des systèmes de taille 20, alors que d'autres méthodes iront bien au-delà. Les ordinateurs, quels qu'ils soient —ceux de 1950, comme ceux d'aujourd'hui ou ceux de 2100— buttent sur des limites et c'est à cette évidence là qu'est confronté celui qui écrit des algorithmes et qui ne peut donc jamais raisonner (contrairement à ce que fait le débutant en programmation) en se disant que la puissance de la machine suppléera au manque d'analyse préalable. La règle véritable, opposée à l'idée première, est donc que : plus une machine est puissante plus il y a de travail mathématique préalable à mener pour la faire fonctionner correctement.

Un problème aussi simple que la multiplication des nombres entiers conduit au développement de méthodes complexes et délicates quand on doit manipuler des nombres de grandes tailles possédant plusieurs milliers ou millions de chiffres. On a été étonné en s'apercevant que sur une question aussi élémentaire des progrès étaient possibles. Pourtant dans la décennie 1970 on a mis au point des méthodes permettant de multiplier deux nombres de n chiffres en un temps proportionnel à n.ln(n).ln(ln(n)) ce qui en pratique est presque équivalent à un temps proportionnel à n et est bien plus rapide que les méthodes classiques tirées des procédures pratiquées à la main depuis des millénaires qui, elles, demandent un temps de travail proportionnel à n2 ou ou n3. Ce que vous pouvez faire avec le bon algorithme de multiplication contemporain, sans lui et en ne comptant que sur la loi de Moore (qui prédit un doublement de la puissance des ordinateurs tous les 18 mois) il vous faudrait attendre 2050 ou plus pour y parvenir.

Records pulvérisés grâce aux théoriciens

Grâce à cette algorithmique sans cesse revisitée complétée et méticuleusement perfectionnée autant qu'aux progrès de l'électronique, on a pu progresser dans le calcul des constantes mathématiques et arriver à obtenir plusieurs milliards de décimales des principales d'entre elles (Pi, e, racine de 2, le nombre d'or, etc.). Ces progrès algorithmiques se sont parfois accompagnés de surprises comme la découverte par une équipe canadienne en 1995 (en s'aidant d'un ordinateur) d'une nouvelle formule pour le calcul de Pi et d'une méthode exploitant cette formule permettant de calculer les chiffres binaires de Pi indépendamment les uns des autres, ce que tout le monde croyait impossible. Cet exploit théorique a été transformé en exploit pratique par Colin Percival qui en septembre 2000 a obtenu une petite tranche de chiffres binaires de Pi autour du 1015-ème chiffre binaire de Pi, performance qui auparavant semblait hors de portée pour des siècles : un bon algorithme rend possible ce qui sans lui ne l'est pas.

Comme autres conséquences de cette maîtrise algorithmique des calculs arithmétiques avec des nombres de grande taille, il faut citer la découverte de nombres premiers records : un nombre premier de deux millions de chiffres en 1999 et un autre de 4 millions de chiffres en 2001 et récemment de plus de 10 millions de chiffres. Là encore, la découverte des tests probabilistes de primalité (qui vous indiquent sans certitude absolue mais avec un risque d'erreur infinitésimal qu'un nombre entier est premier) fut une surprise théorique, par ailleurs d'une grande utilité en cryptographie.

Depuis deux décennies et au-delà des exploits informatiques parfois anecdotiques, c'est toute une science de l'organisation des calculs qui a connu des progrès considérables et a atteint la maturité tissant des liens profonds avec les mathématiques et changeant parfois radicalement les points de vue. Des livres d'arithmétique d'un genre nouveau sont apparus dans lesquels les concepts introduits sont systématiquement associés à des outils algorithmiques permettant de les manipuler réellement et efficacement avec un ordinateur. Les mathématiques sont nécessaires à la maîtrise des ordinateurs et contribuent en profondeur à leur compréhension, mais, en retour, les ordinateurs conduisent à pratiquer les mathématiques de manière différente et donne une vue nouvelle des objets abstraits que la machine —pourvu qu'on l'instruise pour cela— manipule mieux que l'esprit humain et en tout cas avec une précision et une sûreté incomparables.

Ce n'est pas seulement l'arithmétique mais une partie importante des mathématiques qui est concernée par les progrès de l'algorithmique. Le calcul formel (domaine où l'on demande à l'ordinateur de calculer non plus seulement avec des nombres mais aussi avec des symboles, des fonctions, des équations, des matrices, etc.) s'est considérablement développé et s'est maintenant introduit dans les lycées et sur le bureau des ingénieurs. L'irruption de l'ordinateur dans le monde des objets abstraits engendre une multitude de nouvelles pratiques mathématiques.

Les applications stimulent les théoriciens

Suscités par les progrès des algorithmes et des machines, hors des mathématiques pures, des domaines d'applications nouveaux sont apparus qui en retour ont exigé des théoriciens des explorations nouvelles. A titre d'exemple citons la phylogénie qui est l'art de reconstituer les arbres généalogiques des espèces vivantes : elle s'est vue radicalement transformée. Autrefois les données morphologiques ou moléculaires étaient traitées à la main par des méthodes nécessairement limitées en complexité. Depuis une trentaine d'années, l'utilisation des ordinateurs non seulement a permis d'envisager des jeux de données plus volumineux, mais a aussi permis l'utilisation de méthodes bien plus complexes et performantes. Des algorithmes nouveaux, fondés sur des idées nouvelles et des résultats particuliers de la théorie des graphes et des arbres, associés à des résultats de statistiques et de modélisation sont aujourd'hui au cœur de cette discipline transfigurée par l'intrusion de l'informatique et des mathématiques au plus profond de son fonctionnement. Plus généralement, le traitement des données de la biologie moléculaire a engendré des développements théoriques et algorithmiques nombreux donnant naissance à un domaine scientifique mi-théorique mi-pratique, la bioinformatique, qui prend de plus en plus d'importance et qui contribuera peut-être à une mathématisation de la biologie analogue à celle que connaît depuis longtemps la physique.

La logique mathématique ouvre des perspectives

Dans ce domaine si foisonnant de l'algorithmique, il faut mentionner les recherches basées sur la logique mathématique qui font envisager la programmation avec un regard différent.

L'idée de la programmation déclarative formulée au début de la décennie 1970 est que pour faciliter le travail du programmeur on doit seulement lui demander de décrire son problème, la machine se chargera ensuite seule de le résoudre. Dans ce paradigme informatique programmer n'est pas commander mais simplement déclarer. Bien sûr, ce rêve ne peut fonctionner à tout coup : si pour un problème donné plusieurs algorithmes existent, comment la machine doit-elle choisir ? Cependant le langage Prolog, inventé à Marseille par A. Colmérauer et ses collaborateurs, en se fondant sur des techniques de démonstration automatique réussit un compromis entre simplicité et efficacité, autorisant la déclarativité. Ses idées ont été généralisées et continuent de jouer un rôle important dans le domaine de l'Intelligence artificielle et des systèmes experts.

Toujours dans le cadre des applications des concepts de la logique mathématique, une autre voie appelée programmation par les preuves se propose de concevoir la programmation comme un exercice d'écriture de démonstrations (cette approche se fonde sur ce qu'on appelle l'isomorphisme de Curry-Howard qui explicite un parallélisme précis entre preuves et programmes). Le programmeur écrit la démonstration d'une certaine propriété (par exemple que pour toute suite de nombres T il existe une suite S qui possède les mêmes éléments classés par ordre croissant) et à partir de cette preuve la machine engendre un programme dont on peut être certain qu'il ne comportera aucune erreur (ce programme dans notre exemple classera les éléments d'une suite T par ordre croissant, ce qui donnera S). Cette approche prometteuse pour la mise au point de logiciels sans erreur a déjà à son actif plusieurs réussites dans le domaine de la certification des programmes et de circuits.

Au-delà  de ces deux idées la logique joue aujourd'hui un rôle important en Intelligence artificielle où toutes sortes d'études ont été menées et appliquées au sujet de ce qu'on appelle les logiques non-classiques dont le but est de suivre au plus près le raisonnement humain plus complexe que le raisonnement mathématique pur. Les logiques paraconsistantes permettent de traiter des données comportant des contradictions ; les logiques non-monotones considèrent que ce qui est déduit peut être invalidés lorsque des informations nouvelles surviennent ; les logiques floues, partielles, multivaluées, modales refusent l'idée classique que tout est vrai ou faux, etc.

La leçon de ces approches tirées de la logique mathématique est que la programmation des ordinateurs doit être abordée sous une multitude d'angles différents et qu'un bon algorithme est d'abord une idée, mieux une vision. Toute théorie mathématique y compris la plus abstraite est susceptible de produire des algorithmes utiles.

Les développements de l'algorithmique ont d'ailleurs pris toutes sortes de formes impossibles à mentionner dans le détail. Citons quelques domaines, objets de travaux intenses ces dernières années : l'algorithmique pour le parallélisme c'est-à-dire pour la programmation des ordinateurs ayant plusieurs unités de calcul ; l'algorithmique distribuée qui permet la maîtrise des réseaux ; l'algorithmique pour les images de synthèse produisant en particulier les fameuses et époustouflantes visions mathématiques que sont les fractales ; les algorithmes de compression de données dont l'importance pratique est sans cesse confirmée ; l'analyse d'algorithmes, objets de beaux travaux mathématiques (analyse dans le pire des cas, analyse dans le cas moyen, etc.) ; les algorithmes probabilistes qui supposent que l'ordinateur dispose d'une source de chiffres aléatoires ; les algorithmes génétiques fondés sur l'exploitation de la métaphore variation-sélection empruntée à la théorie de l'évolution ; les réseaux neuronaux qui conduisent à la mise au point d'algorithmes d'apprentissage automatique analogues (autant qu'on puisse le savoir) à ceux à l'œuvre dans les cerveaux des organismes vivants.

La cryptographie envahit l'informatique

Cependant s'appuyant parfois sur les progrès de l'algorithmique arithmétique (et agissant en stimulant sur eux), la cryptographie plus que tout autre domaine a connu depuis trois décennies une authentique révolution et est devenue une discipline civile (elle était auparavant aux mains des militaires) et centrale de l'informatique.

L'idée la plus importante est celle de la cryptographie à double clef (ou cryptographie asymétrique). Cette idée née il y a trente ans a atteint maintenant sa maturité. Il s'agit de proposer des méthodes où la transformation du message clair en message chiffré se fait à l'aide d'une clef mise à la disposition de tout le monde (la clef publique) ; la transformation inverse permettant de retrouver le message clair à partir du message chiffré nécessite en revanche la connaissance d'une clef qui restera secrète. Cette clef privée est associée à la clef publique sans qu'aucun moyen simple ne permette de la déduire de la clef publique. Avec cette invention remarquable dont le protocole RSA (initiales de Rivest, Shamir, Adleman) est la version la plus aboutie et la mieux maîtrisée, on peut communiquer de manière secrète avec un interlocuteur sans avoir à  procéder à un échange préalable de clefs secrètes. Mais, et c'est aussi important, grâce à ces méthodes, on peut signer des messages, ou programmer des systèmes d'authentification. D'autres recherches en cryptographie ont conduit à la mise au point de générateurs pseudo-aléatoires efficaces et sûrs et permettent une maîtrise améliorée des protocoles à simple clef (la clef de chiffrage est la même que la clef de déchiffrage).

Ces découvertes mathématiques fondamentales et réellement importantes sur le plan pratique sont merveilleuses, elles montrent à quel point la maîtrise des concepts de l'arithmétique (qui longtemps a eu la réputation d'être une science de l'inutile) et de la théorie de l'information peut se révéler importante pour le développement de l'informatique, et aujourd'hui chacun doit savoir que l'utilisation d'une carte bancaire à puce ou le paiement par internet mettent en jeu des mathématiques de haut niveau.

Pourtant, quelles que soient les découvertes faites, il se trouve que certaines questions restent mal résolues. La sûreté de nombreux algorithmes de cryptographie repose sur l'affirmation qu'un certain problème est intrinsèquement difficile à résoudre (voir plus bas des précisions sur cette notion). Par exemple la sûreté du RSA s'appuie sur le problème de la factorisation des grands nombres. Or la preuve que la factorisation des grands nombres est intrinsèquement difficile n'a pour l'instant pas été apportée et même si elle n'est guère mise en doute c'est un fait que la démonstration manque. Du coup, contrairement à ce qu'on présente souvent au public pour simplifier les exposés, la sûreté de nombreuses méthodes de cryptographie reste suspendue à des résultats mathématiques manquants. Cette situation permet de dire qu'il faut encore plus d'informatique théorique et en particulier qu'il faut approfondir encore les concepts les plus abstraits de la théorie du calcul pour accroître la sécurité des protocoles cryptographiques dont chacun à besoin. L'informatique théorique n'est pas une danseuse coûteuse et inutile destinée à procurer des satisfactions intellectuelles à des chercheurs désœuvrés, mais une science fondamentale dont on attend les avancées avec impatience et sans laquelle notre monde ne serait pas ce qu'il est.

Obstructions graves en théorie de la complexité

Au cœur justement de l'informatique théorique, la théorie du calcul —ou théorie de la calculabilité— née dans la décennie 1930 répond à des questions sur ce qui est faisable et sur ce qui ne l'est pas dans l'absolu avec un ordinateur. Elle énonce des résultats négatifs du type : il est impossible d'écrire un programme qui, chargé d'analyser d'autres programmes, repère ceux qui calculent la même fonction (indécidabilité de l'équivalence des programmes). Ces preuves d'impossibilité sont importantes sur le plan général et de nombreux résultats de ce type continuent à être produits. Une partition de plus en plus précise, tranchant entre l'algorithmiquement faisable et l'impossible du calcul, est maintenant disponible, éclairant de nombreux problèmes pratiques et mathématiques.

Ce domaine ancien sans cesse complété a ouvert la voie depuis trente ans à une analyse d'un niveau plus fin encore, où l'on se pose des  questions du type : peut-on décomposer en facteurs premiers un nombre de n chiffres en utilisant un temps de calcul  proportionnel à un polynôme en n (on parle de temps polynomial) ? Les problèmes qu'on peut traiter en temps polynomial constituent la classe de complexité P. On considère qu'un problème dans la classe P est non seulement algorithmiquement traitable mais efficacement traitable ; dans le cas contraire, on considère que le problème est intrinsèquement difficile. Bien sûr, connaître la classe P est important.

La question suivante est différente de la précédente : connaissant une éventuelle décomposition d'un nombre de n chiffres en facteurs premiers peut-on vérifier qu'elle est correcte en temps polynomial ? Les problèmes dont on peut ainsi vérifier les solutions en temps polynomial constituent la classe NP. On sait aujourd'hui que le problème de la factorisation est dans la classe NP, mais pour la classe P on ignore la réponse même si on pense qu'elle est négative. C'est une question importante pour la cryptographie comme je l'indiquais plus haut.

Il semble évident que la classe NP n'est pas identique à la classe P —car il est certainement plus facile de vérifier une solution proposée que de la trouver ! Pourtant la démonstration de l'affirmation P≠NP est l'une des énigmes les plus récalcitrantes de la théorie des classes de complexité. Un prix d'un million de dollars a d'ailleurs été offert à qui prouvera ce résultat ou son contraire : P=NP. Il y a trois décennies, on découvrait ce problème qu'on espérait résoudre rapidement, aujourd'hui malgré de multiples tentatives (et le prix !) on cherche toujours en vain à le résoudre.

Cette situation de blocage est franchement gênante, car elle se produit en un point central de la théorie de la complexité : tant que cette question ne sera pas proprement réglée la théorie des classes de complexité sera entravée et aucun des résultats dont on a besoin en cryptographie pour prouver de manière absolue la sûreté des méthodes les plus utilisées ne sera établi. Démontrer par exemple que la factorisation est impossible à traiter en temps polynomial impliquerait que P≠NP et donc démontrer que la factorisation n'est pas polynomiale est plus difficile que démontrer que P≠NP. Tant que P≠NP résiste, il n'y a aucun espoir de prouver le résultat attendu en cryptographie sur la factorisation.

Le travail fait pendant les 25 dernières années dans la théorie des classes de complexité n'a cependant pas été vain : un grand nombre de classes nouvelles ont été identifiées, bien souvent sans réussir à démontrer qu'elles étaient différentes deux à deux. Elles composent un panorama très fin des échelles de difficulté algorithmique, dont on doit espérer qu'il nous achemine vers le déblocage attendu.

Quintessence d'indécidabilité

Ces difficultés mathématiques sont peut-être liées aux résultats logiques d'incomplétude (démontrés par Kurt Gödel en 1931) et dont la compréhension n'a cessé de s'approfondir, en particulier grâce à la théorie de la complexité de Kolmogorov. Celle-ci développe mathématiquement l'idée qu'est complexe ce qui ne peut pas s'exprimer brièvement et ces 30 dernières années a connu des développements remarquables conduisant en particulier à l'élucidation du problème de la définition mathématique des suites aléatoires (posé depuis le début du XXe siècle). Cette définition qui exprime l'idée qu'est aléatoire ce qui est incompressible a conduit à la découverte de la famille extraordinaire des nombres Oméga de Chaitin dont la connaissance a sérieusement progressé durant la dernière décennie. Ces nombres concentrent en eux des propriétés d'indécidabilité remarquables (ils sont transcendants, aléatoires et incalculables) et constituent en quelque sorte un sommet de la théorie de la calculabilité.

Plus étonnant, la théorie de la complexité de Kolmogorov a établi des liens profonds avec la physique et pourrait bien être une clef de la thermodynamique statistique comme C. Bennett et W. Zurek l'ont suggéré récemment. Ces liens entre informatique théorique et physique sont d'ailleurs une des grandes nouveautés de ces dernières années. Non seulement il est apparu que la compréhension du problème du coût énergétique minimum du calcul et des calculs réversibles s'appuie sur eux, mais ils sont aussi à l'origine d'une révolution dont tout laisse prévoir qu'elle occupera une place considérable dans l'avenir : l'introduction de la mécanique quantique en informatique théorique.

Naissance de l'informatique quantique

L'idée est de prendre au sérieux que la vraie théorie de notre monde physique est la mécanique quantique (et non pas la mécanique classique) pour s'interroger sur la physique du calcul. Auparavant, l'hypothèse implicite de toute l'informatique théorique était celle d'un monde newtonien. Cette hypothèse est moins bénigne qu'on le croyait et il a fallu admettre que de nombreux problèmes fondamentaux nécessitent une reformulation quantique.

Citons deux résultats importants obtenus dans cette direction. Le premier concerne encore la cryptographie où l'intrusion de la mécanique quantique a permis de définir des protocoles d'échanges secrets dont la sûreté ne repose plus sur des conjectures mathématiques non démontrées, mais simplement sur l'hypothèse de la validité des lois quantiques. Ces protocoles qui utilisent des photons polarisés ont été concrètement mis en place ces dernières années. Le second résultat découvert en 1994 par Peter Shor, est la preuve qu'un ordinateur quantique peut réaliser la factorisation des entiers en temps polynomial, ce que, comme nous le disions, un ordinateur classique ne peut vraisemblablement pas faire. Cette preuve a deux conséquences. D'abord elle montre que l'introduction des modèles quantiques de calcul change profondément la situation rendant possibles des traitements qui ne le sont pas dans le monde classique (de nouvelles classes de complexité quantiques sont donc venues compléter la famille commencée avec P et NP). Ensuite, cette preuve établit que la mise au point de calculateurs quantiques, dont on ne sait pas aujourd'hui si elle aboutira, entraînerait des bouleversements graves en cryptographie. En fait, c'est une nouvelle conception de l'information et du calcul que suggère la mécanique quantique et c'est une remise en cause profonde des modèles jusqu'ici considérés comme absolus que les théoriciens sont maintenant contraints d'opérer : le modèle de la machine de Turing classique doit laisser la place à celui de la machine de Turing quantique.

Bibliographie

Handbook of Theoretical Computer Science. Édité par J. van Leeuven. Elsevier Science Publishers. 1990. Deux tomes.

M. Nakahara et T. Homi, Quantum Computing, From Linear Algebra to Physical Realizations, CRC-press, 2008.

M. Sipser. Introduction to the Theory of Computation. Thomson, 2006.

J.-P. Delahaye. L'intelligence et le calcul. De Gödel aux ordinateurs quantiques. Éditions Belin/Pour la science, Paris, 2002.

J.-P. Delahaye. Complexités : aux limites des mathématiques et de l'informatique. Éditions Belin/Pour la science, Paris, 2006.

Jean Paul Delahaye
Université des Sciences et Technologies de Lille
Laboratoire d'Informatique Fondamentale de Lille,
UMR-CNRS 8022
59655 Villeneuve d'Ascq  Cedex
courriel : delahaye@lifl.fr