Thèse Complexité Algorithmique des Systèmes Dynamiques Prédiction Atteignabilité et Modèles de Calcul H/F - 75

Établissement : Institut Polytechnique de Paris École polytechnique
École doctorale : Ecole Doctorale de l'Institut Polytechnique de Paris
Laboratoire de recherche : LIX - Laboratoire d'informatique
Direction de la thèse : Olivier BOURNEZ ORCID 0000000292181130
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-08-01T23:59:59Cette thèse vise à développer une théorie de la complexité algorithmique des systèmes dynamiques. Les systèmes dynamiques constituent un cadre mathématique fondamental pour décrire des phénomènes évoluant dans le temps, qu'il s'agisse de systèmes discrets, définis par des itérations de fonctions, ou de systèmes continus décrits par des équations différentielles. Au-delà de leur rôle en modélisation scientifique, des travaux récents ont montré qu'ils peuvent également être interprétés comme des modèles de calcul.

En particulier, plusieurs résultats ont établi des liens profonds entre équations différentielles et complexité computationnelle. Il a notamment été montré que les fonctions calculables en temps polynomial correspondent exactement aux solutions d'équations différentielles polynomiales de longueur polynomiale. Des résultats complémentaires ont également montré que des équations différentielles discrètes permettent de caractériser des classes de complexité telles que PTIME et PSPACE. Ces travaux suggèrent que les systèmes dynamiques constituent un cadre unifié pour décrire le calcul dans des contextes discrets et continus.

Par ailleurs, des systèmes dynamiques simples peuvent présenter des comportements complexes, notamment chaotiques, caractérisés par une forte sensibilité aux conditions initiales et des dynamiques à long terme difficiles à prédire. Ces phénomènes soulèvent naturellement des questions algorithmiques fondamentales : quelle est la complexité de la prédiction de l'évolution d'un système dynamique ? quelles sont les propriétés de calcul associées à ces systèmes ? quelles classes de complexité peuvent-ils caractériser ?

Des développements récents en apprentissage automatique renforcent également ces liens. Les réseaux de neurones peuvent être interprétés comme des systèmes dynamiques discrets, tandis que les neural ordinary differential equations correspondent à des systèmes dynamiques continus. Cette perspective suggère une approche unifiée où équations différentielles, systèmes dynamiques discrets et réseaux de neurones sont étudiés comme des modèles de calcul.

L'objectif de la thèse est d'étudier la complexité algorithmique de systèmes dynamiques simples, notamment en dimension fixée, et d'analyser les problèmes algorithmiques naturels associés à ces systèmes. Les axes principaux incluent l'étude de la complexité de la prédiction de trajectoires, l'analyse de problèmes d'atteignabilité, l'exploration du lien entre chaos et complexité computationnelle, ainsi que l'étude des réseaux de neurones comme systèmes dynamiques.

Les résultats attendus devraient contribuer à mieux comprendre le rôle des systèmes dynamiques comme modèles de calcul et à développer une théorie de la complexité pour ces systèmes, en reliant complexité computationnelle, systèmes dynamiques et apprentissage automatique.

Des travaux récents ont établi des liens profonds entre systèmes dynamiques et complexité computationnelle. En particulier, il a été montré que les fonctions calculables en temps polynomial correspondent exactement aux solutions d'équations différentielles polynomiales de longueur polynomiale \cite{JournalACM2017}. Des résultats complémentaires ont montré que des équations différentielles discrètes permettent également de caractériser des classes de complexité telles que PTIME et PSPACE \cite{MFCSJournal,BlancBournezMFCS2023Journal}.

Ces travaux suggèrent que les systèmes dynamiques constituent un cadre unifié pour étudier le calcul dans des contextes continus et discrets. Par ailleurs, des systèmes dynamiques simples peuvent exhiber des comportements complexes, notamment chaotiques \cite{Dev87}, ce qui soulève des questions algorithmiques naturelles concernant la prédiction de leur évolution.

Enfin, les développements récents en apprentissage automatique renforcent ces liens : les réseaux de neurones peuvent être interprétés comme des systèmes dynamiques discrets \cite{SS95}, tandis que les neural ordinary differential equations correspondent à des systèmes dynamiques continus \cite{chen2018neural}. Ces connexions ouvrent de nouvelles perspectives pour l'étude de la complexité des systèmes dynamiques.

\bigskip

\textbf{Méthode}

L'objectif principal de la thèse est de développer une théorie de la complexité algorithmique des systèmes dynamiques simples. Il s'agit en particulier d'étudier dans quelle mesure des systèmes dynamiques de dimension fixée peuvent servir de modèles de calcul et caractériser des classes de complexité classiques.

Plusieurs objectifs scientifiques structurent le projet :
\begin{itemize}
\item comprendre comment des systèmes dynamiques simples peuvent simuler des calculs complexes ;
\item étudier la complexité algorithmique de problèmes naturels associés aux systèmes dynamiques, notamment les problèmes de prédiction et d'atteignabilité ;
\item analyser les liens entre comportement chaotique et complexité computationnelle ;
\item étudier les réseaux de neurones comme systèmes dynamiques et comparer leur puissance de calcul avec celle de modèles issus du calcul analogique.
\end{itemize}

La thèse s'appuiera principalement sur des outils issus de la théorie de la complexité, de la calculabilité sur les réels et de l'analyse des systèmes dynamiques. Les approches combinent :

\begin{itemize}
\item l'étude formelle de modèles de calcul définis par des systèmes dynamiques (équations différentielles polynomiales, systèmes dynamiques discrets, réseaux de neurones) ;
\item l'analyse de problèmes algorithmiques associés à ces systèmes (prédiction, atteignabilité) ;
\item la construction de simulations de modèles de calcul classiques par des systèmes dynamiques ;
\item l'établissement de résultats de complexité et de bornes de calcul pour ces modèles.
\end{itemize}