Un nouveau point de vue pour étudier la complexité
Combien font quatre fois l’arctangente de 1 ? Pas de panique : vous obtiendrez rapidement une approximation numérique de la réponse –en l’occurrence, pi– si vous avez une calculette à portée de main (ou de très bons souvenirs de trigonométrie). Mais, au fond, ce calcul est-il facile ou difficile ? La question n’est pas si simple ! Classer et comparer les problèmes selon leur degré de difficulté constitue un domaine à part entière de l’informatique avec des enjeux à la fois pratiques et fondamentaux : la théorie de la complexité. Manon Blanc, doctorante au Laboratoire d'informatique de l'École polytechnique (LIX*) étudie ces classes de complexités et vient d’être récompensée avec son co-directeur de thèse Olivier Bournez par le prix du meilleur article lors de la conférence internationale Mathematical Foundations of Computer Science.
Un autre formalisme que celui de Turing
Une classe de complexité regroupe tous les problèmes qui requièrent une quantité de ressources (comme le temps de calcul, la mémoire) similaire pour être résolus. Ainsi, si le temps nécessaire à un calcul croît de façon exponentielle avec le nombre de données d’entrée de ce calcul, alors ce problème sera de complexité exponentielle en temps (classe EXPTIME), et donc très difficile à résoudre. En pratique, on considère par convention que les problèmes « faciles », qui peuvent être résolus en un temps raisonnable, ont une complexité qui croît comme un polynôme avec le nombre de données d’entrée (classe P pour polynômiale).
Cette convention a été fixée pour que la complexité ne dépende que du problème lui-même et pas, par exemple, de la puissance de l’ordinateur utilisé pour le calcul. Il faut donc définir précisément ces classes de complexité. Pour cela, les scientifiques font généralement appel au formalisme des machines de Turing, développé par Alan Turing, un des principaux informaticiens du XXe siècle. Les machines de Turing permettent de décomposer chaque problème en opérations élémentaires sur des nombres binaires, avec certaines règles. Le temps de calcul est défini en comptant le nombre d’étapes nécessaires à la résolution. « Mais il existe d’autres point de vue sous lesquels étudier les classes de complexité et c’est l’objectif de ma thèse » explique Manon Blanc.
Dans leur article, Manon Blanc et Olivier Bournez proposent une caractérisation permettant de savoir si une fonction prenant en entrée des nombres réels est calculable en temps polynomial (et, d’autre part, si la mémoire nécessaire pour le calcul croît de façon polynomiale). Par exemple, la fonction arctangente, comme la plupart des fonctions usuelles, est bien dans la classe P. Si on voulait le montrer avec les machines de Turing, il faudrait d’abord expliquer comment la calculer cette fonction, décrire un programme capable de l’approximer, le décomposer en étape avec le formalisme adéquat… Avec ce nouveau résultat, il suffit de montrer que la fonction appartient à un groupe simple de fonctions dont les propriétés sont présentées dans l’article des deux chercheurs.
Un intérêt fondamental et pédagogique
Cette nouvelle façon de voir les classes de complexité découle d’une question originale dans ce domaine : que peut-on calculer avec des ordinateurs, qui ne travaillent pas en binaire, mais sur des quantités analogiques ? « Nos ordinateurs travaillent avec une logique binaire : 0 ou 1. Mais ils sont faits de composants électroniques, dont la physique n’est pas décrite de façon binaire mais par des équations différentielles. Rien n’empêche de construire des ordinateurs analogiques » explique Olivier Bournez, qui en possède plusieurs dans son bureau et mène des recherches sur ces questions depuis plusieurs années. C’est en reprenant ces idées, et notamment cet outil que constituent les équations différentielles, qu’ils ont obtenu ce résultat. Outre son intérêt fondamental, les auteurs y voient un caractère pédagogique : permettre de parler de complexité à des étudiants souvent plus à l’aise avec le concept de fonctions, enseigné dès le secondaire, que celui de machines de Turing. Manon Blanc, qui compte bien continuer l’étude de la complexité sous différents points de vue, y trouve un intérêt supplémentaire : « ce sont avant tout des jolies maths, et de la jolie informatique théorique, qui m’amusent ! »