Circuits algébriques, Complexité de calcul, Procédures de décision, Suites hypergéométriques, Test d'identité dans les corps de nombres, Algorithmes randomisés, Atteignabilité

Les modèles polynomiaux sont omniprésents en informatique, dans l'étude des automates et des langages formels, de l'optimisation, de la théorie des jeux, de la théorie du contrôle et de nombreux autres domaines. Dans cette thèse, nous considérons des modèles décrits par des systèmes d'équations polynomiales et des équations différentielles, où le système évolue à travers un ensemble discret de pas de temps avec des mises à jour polynomiales à chaque pas. Nous explorons trois aspects des « problèmes de zéros » pour les modèles polynomiaux : le test d'identité pour les expressions algébriques données par des polynômes, la détermination de l'existence de racines pour les systèmes polynomiaux et la détermination de l'existence de zéros dans les suites satisfaisant des récurrences à coefficients polynomiaux. Dans la première partie, nous étudions les tests d'identité pour les expressions algébriques impliquant des radicaux. En d'autres termes, étant donné un polynôme à k variables représenté par un circuit algébrique et k radicaux réels, nous examinons la complexité de déterminer si le polynôme s'annule sur l'entrée. Nous améliorons la borne PSPACE existante, en plaçant le problème dans coNP en supposant l'hypothèse de Riemann généralisée (HRG). Nous considérons ensuite une version restreinte du problème, où les entrées sont des racines carrées de nombres premiers impairs, montrant qu'il peut être résolu en temps polynomial randomisé en supposant HRG. Nous considérons ensuite les systèmes d'équations polynomiales et étudions la complexité de déterminer si un système de polynômes à coefficients polynomials a une solution. Nous présentons une approche du problème basée sur la théorie des nombres, généralisant les techniques utilisées pour les tests d'identité, et montrons que le problème appartient à la classe de complexité AM en supposant HRG. Nous analysons le lien entre ce problème et le problème de la détermination de la dimension d'une variété complexe, dont l'appartenance à AM a déjà été prouvé supposant HRG. Dans la dernière partie de cette thèse, nous analysons les suites satisfaisant des récurrences à coefficients polynomiaux. Nous étudions la question de savoir si zéro appartient d'une suite récursive polynomiale résultant d'une somme de deux suites hypergéométriques. Plus précisément, nous considérons le problème pour les suites dont les coefficients polynomiaux se décomposent dans le corps des rationnels Q. Nous montrons sa relation avec les valeurs de la fonction Gamma évaluées en des points rationnels, ce qui permet d'établir la décidabilité du problème supposant la conjecture de Rohrlich-Lang. Nous proposons une nouvelle approche basée sur l'étude des diviseurs premiers de la suite, ce qui nous permet d'établir la décidabilité inconditionnelle du problème.