Thèse Complexes de Solutions Algorithmes et Complexité H/F - Doctorat.Gouv.Fr

Établissement : Université Grenoble Alpes
École doctorale : MSTII - Mathématiques, Sciences et technologies de l'information, Informatique
Laboratoire de recherche : Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Direction de la thèse : Zoltan SZIGETI ORCID 0000000329821737
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-06-09T23:59:59

L'objectif du projet de thèse est de développer un lien fondamental entre la complexité des problèmes de l'informatique théorique et certains caractéristiques topologiques de leurs solutions. L'idée générale est de montrer qu'un problème admet un algorithme efficace si ses solutions forment un structure topologique simple et sinon, un tel algorithme n'existe pas sous des hypothèses de complexité standard. Des résultats récents ont confirmé un tel comportement pour le problème de satisfaction de contraintes (CSP), un problème important de l'informatique théorique avec des applications par exemple en Intelligence Artificielle (IA) et en Recherche Opérationnelle (RO), ainsi que des cas spéciaux connus comme le problème de la satisfaisabilité Booléenne (SAT) et le problème d'homomorphismes de graphes. L'objectif de cette thèse est d'étendre l'approche topologique ci-dessus à d'autres classes problèmes que le CSP. On va considérer comme points de départ le problème de formules Booléennes quantifiées et le problème SAT Reconfiguration. Pour ces deux problèmes, des classifications complètes de leur complexité sont connues grâce à d'approches non-topologiques et notre premier but est d'obtenir une version topologique de ces résultats. Ensuite, on propose d'étendre ces résultats à des problèmes par exemple au CSP quantifié (QCSP), qui est actuellement un sujet brûlant en complexité computationnelle et qui est au-delà de l'état de l'art actuel des méthodes non-topologiques.

complexité de problèmes fondamentaux de l'informatique théorique, voir le pdf en PJ pour le contexte détaillé

Le candidat doit posséder de solides connaissances en informatique théorique (algorithmes et complexité, théorie des graphes) et un intérêt général pour les mathématiques.