Le temps comme une longueur de courbe

Distinctions Informatique

Amaury Pouly reçoit le prix Ackermann qui récompense chaque année au niveau européen une thèse exceptionnelle dans les domaines de la logique et de la science informatique. Ses travaux, qui reposent sur la comparaison des modèles théoriques analogiques et digitaux, proposent une nouvelle vision de la complexité algorithmique, considérant le temps nécessaire à la résolution d’un problème comme la longueur de courbe d’une équation différentielle. Ces apports offrent un nouvel éclairage sur une problématique fondamentale en informatique théorique.

P = NP. Cette affirmation ne vous dit rien ? Elle est pourtant au cœur de l’informatique théorique, et la résolution de cette problématique aurait des conséquences très importantes dans notre vie quotidienne ! Pour bien comprendre cette question fondamentale, il faut revenir aux sources de l’informatique théorique, cette discipline qui cherche à mesurer l’efficacité des algorithmes à partir du nombre de pas de calcul (petites étapes de calcul) nécessaires pour résoudre des problèmes. En étudiant un modèle théorique des ordinateurs, symbolisé par la machine de Turing, les chercheurs ont pu ranger les problèmes en plusieurs classes. Parmi ces catégories, distingue traditionnellement les problèmes que l’on peut résoudre dans un temps appelé polynomial (la classe dite P), ce qui signifie dans un temps efficace ou du moins acceptable, et les problèmes dont on peut vérifier les solutions lorsqu’elles sont trouvées en temps polynomial (classe dite NP). Ces deux classes de complexité sont définies de manière différente et la question de savoir si ces deux classes sont effectivement distinctes est centrale pour un nombre très important d’outils numériques. C’est le cas notamment de la cryptographie. En effet, chiffrer des informations demande de s’appuyer sur des problèmes impossibles à résoudre par des attaquants. Mais comme les chercheurs ne sont pas certains que cette distinction existe réellement, potentiellement tous les problèmes pourraient être un jour résolus dans un temps polynomial grâce à un outil mathématique non encore découvert !

Les recherches d’Amaury Pouly1 , qui viennent de recevoir le prix Ackermann décerné par l’European Association for Computer Science Logic (EACSL), participent à cette quête d’une manière originale. Comme évoqué, les chercheurs en informatique théorique s’appuient sur un modèle théorique des ordinateurs qui a été décrit par Alan Turing. Cette machine de Turing fonctionne avec des pas de calcul pour effectuer des opérations. C’est l’accumulation de ces pas de calcul qui permet la résolution d’un problème. Le fait qu’il y ait des pas de calcul, des étapes que l’on peut délimiter, définit ce modèle comme « discret ». Or, historiquement, les premiers ordinateurs avaient au contraire un fonctionnement continu (sans étapes claires). Une machine, appelée analyseur différentiel, construite dans les années 1930 pour résoudre des équations différentielles, était par exemple constituée de manivelles, de disques et d’engrenages. Claude Shannon avait défini un modèle théorique à partir de cette machine qu’il avait appelé GPAC pour General Purpose Analog Computer. Mais la communauté scientifique avait rapidement abandonné ce modèle continu, estimant qu’il était trop limité et que la machine de Turing, le modèle discret homologue, permettait de résoudre plus de problèmes.

Image retirée.
Un analyseur différentiel au NACA Lewis Flight Propulsion Laboratory en 1951


Ces résultats ont été contestés par Olivier Bournez, Daniel Graça et deux autres chercheurs, qui ont démontré qu’avec une notion de calcul plus moderne, le GPAC montre des capacités égales à la machine de Turing. La comparaison de la complexité, le temps nécessaire pour résoudre un problème, de ces deux modèles n’avait pas encore été faite. C’est sur ce point qu’Amaury Pouly a travaillé au cours de sa thèse, co-encadrée par Olivier Bournez au Laboratoire d’Informatique de l’École polytechnique (LIX - CNRS/École polytechnique), et Daniel Graça de l’Université d’Algarve au Portugal. Les résultats surprenants d’Amaury Pouly ont montré que d’un point de vue théorique, les modèles continus permettent d’obtenir les mêmes résultats en termes de rapidité de calcul que les modèles discrets. C’est-à-dire que ce l’on calcule sur nos ordinateurs modernes et digitaux pourrait l’être aussi sur un modèle analogique mécanique à cylindres !

Ces travaux d’Amaury Pouly établissent aussi un apport remarquable entre temps de calcul et solutions d’équations différentielles. Comme évoqué, le modèle GPAC se basait sur une machine qui servait à calculer des équations différentielles, c’est-à-dire des équations qui relient des fonctions et leurs dérivées. Amaury Pouly a montré que l’on peut définir la notion de ce qui est calculable en temps polynomial (classe P) par des équations différentielles. Cet outil mathématique, très employé en physique, se retrouve donc relié à un problème d’informatique théorique de façon inattendue. Ainsi, Amaury Pouly parvient à définir ce qui est programmable et calculable sans aucune référence à un programme informatique ! Le chercheur exploite le fait que la solution d’une équation différentielle se traduit par une courbe et il démontre que le temps polynomial de calcul de résolution d’un problème correspond à la longueur de cette courbe. Le temps correspond ainsi à une longueur.

Ces apports fournissent de nouveaux outils pour résoudre des problèmes de la classe P, notamment dans des disciplines expérimentales comme la physique, les mathématiques ou la bioinformatique où ces résultats ont permis de caractériser ce que l’on peut calculer avec des réactions chimiques. De façon plus large, ces recherches proposent un nouvel éclairage, un nouvel angle d’attaque, pour résoudre la question P = NP.

Thèse : Continuous models of computation : from computability to complexity d’Amaury Pouly

  • 1Désormais en post-doctorat au Max Planck Institute