Complexes de solutions : Algorithmes et Complexité // Solution Complexes: Algorithms and Complexity

Complexes de solutions: Algorithmes et Complexité // Solution Complexes: Algorithms and Complexity

Réf ABG- ADUM-75246 Sujet de Thèse

Université Grenoble Alpes

Lieu de travail GRENOBLE Cedex 1 - Auvergne-Rhône-Alpes - France

Intitulé du sujet Complexes de solutions : Algorithmes et Complexité // Solution Complexes: Algorithms and Complexity

Champs scientifiques

• Informatique

Mots clés : Complexes simpliciaux, Algorithmique, Complexité, Simplicial Complexes, Algorithms, Complexity

Description du sujet

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 une 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 de 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 à des 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.

Début de la thèse : 01/10/2026

Nature du financement

Précisions sur le financement

Concours allocations

Présentation établissement et labo d'accueil

Université Grenoble Alpes

Etablissement délivrant le doctorat

Université Grenoble Alpes

Ecole doctorale

217 MSTII - Mathématiques, Sciences et technologies de l'information, Informatique

Profil du candidat

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. The candidate should have a strong background in theoretical computer science (algorithms and complexity, graph theory) and a general interest in mathematics.