“Les polynômes sont les éléments constitutifs de nombreux modèles mathématiques en physique, chimie, biologie, économie, et dans de nombreuses autres disciplines ; calculer avec des polynômes est fondamental. En effet, nous apprenons tous à résoudre des équations quadratiques à l’école — mais comment feriez-vous pour trouver les zéros d’un polynôme de degré supérieur ? Ou mieux encore, pour résoudre tout un système d’équations polynomiales ? Klara Nosan, ancienne doctorante à l'IRIF.

Lien de sa thèse : les problèmes de zéros dans les modèles polynomiaux

Je m'appelle Klara et j'ai récemment soutenue ma thèse à l'IRIF. Avant de commencer mon doctorat, j'ai obtenu ma licence en informatique à l'Université de Ljubljana. J'ai ensuite poursuivi avec une première année de master à l'École Polytechnique, puis la deuxième au MPRI (Master Parisien de Recherche en Informatique). J'ai rencontré mes directeurs de thèse, Mahsa Shirmohammadi et James Worrell, au cours de mes stages de recherche de master et, en octobre 2021, j'ai commencé mon doctorat avec eux.

Lorsque j'étais à l'école, j'aimais beaucoup résoudre des problèmes mathématiques. Mais à la fin du lycée, je n'étais plus sûre de vouloir étudier les mathématiques pures et j'ai donc opté pour l'informatique, qui implique aussi beaucoup de raisonnement logique. Au fur et à mesure que j'avançais dans mes études, je me suis rendue compte que j'aimais surtout les aspects théoriques de l'informatique, et j'ai fini par faire de la recherche sur les problèmes de calcul des problèmes mathématiques — ce qui n'est pas très loin de ce que j'aimais faire quand j'étais plus jeune !

Dans ma thèse, j'ai étudié la complexité et la décidabilité des problèmes de calcul dans les modèles polynomiaux. Je me suis concentrée, en particulier, sur les problèmes de zéros dans ces modèles.

Les polynômes sont les éléments constitutifs de nombreux modèles mathématiques en physique, chimie, biologie, économie, et dans de nombreuses autres disciplines ; calculer avec des polynômes est fondamental. En effet, nous apprenons tous à résoudre des équations quadratiques à l’école — mais comment feriez-vous pour trouver les zéros d’un polynôme de degré supérieur ? Ou mieux encore, pour résoudre tout un système d’équations polynomiales ?

Ces questions, apparemment simples, sont parmi les problèmes les plus classiques des mathématiques. Au début du XIXe siècle, par exemple, le résultat révolutionnaire d'Évariste Galois a été de caractériser les polynômes qui sont résolubles par radicaux. À la fin du même siècle, David Hilbert donne une condition caractérisant quand un système d’équations polynomiales n’est pas satisfaisable.

Avec le développement de l’informatique au XXe siècle, un nouveau point de vue sur les problèmes liés aux polynômes est apparu. Dans le contexte du calcul, de nombreuses nouvelles questions se posent : comment pouvons-nous représenter les polynômes de manière succincte ? Et quelle est la complexité de calcul avec de telles représentations succinctes ? Ici, calculer implique aussi bien déterminer si un polynôme s’annule sur une entrée donnée que trouver les zéros de polynômes, ou déterminer la satisfaisabilité de systèmes polynomiaux. Ces problèmes sont centraux dans la théorie de la complexité algébrique.

Dans ma thèse, j’ai étudié trois aspects distincts des problèmes zéro dans les modèles polynomiaux. Le premier est le problème de l'évaluation : étant donné un polynôme à n variables et n valeurs d'entrée, le polynôme s’annule-t-il sur l'entrée donnée ? Le deuxième concerne la satisfiabilité : étant donné un système de polynômes à n variables, existe-t-il un ensemble de n valeurs qui satisfont le système ? Enfin, le problème d’atteignabilité : étant donné une suite de nombres définie par une récurrence à coefficients polynomiaux, le zéro apparaît-il dans la suite ?

En général, la complexité de calcul peut être considérée comme un cadre qui nous aide à comprendre, à partir d'un problème que nous voulons résoudre, l'efficacité de l'algorithme que nous pouvons concevoir pour ce problème. C'est important, car cela nous aide à identifier les problèmes pour lesquels il peut être intéressant de concevoir des algorithmes approximatifs efficaces, une fois que nous savons que nous ne pouvons pas calculer la solution exacte de manière efficace. Les problèmes qui n'admettent pas d'algorithmes efficaces, par exemple, peuvent également être utilisés pour construire des protocoles cryptographiques. L'objectif est donc de classer les problèmes en fonction de leur complexité et d'identifier ceux qui admettent des algorithmes efficaces et ceux qui n'en admettent pas. Je suis contente d'avoir pu compléter une partie de cette compréhension globale pour les problèmes que j'ai étudié dans ma thèse.

Comme je l'ai mentionné au début, j'oscille entre travaux appliqués et théoriques depuis que je suis jeune. J'envisage donc actuellement de faire davantage de recherche appliquée et de voir où cela me mènera.