Complexes de solutions: algorithmes et complexité // solution complexes: algorithms and complexity

Topic description

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.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The goal of the PhD research project is to develop a fundamental link between computational complexity and topological features of computational problems. The general idea is that a computational problem admits an efficient algorithm if its solutions form a topologically simple structure and otherwise no efficient algorithm exists under standard complexity assumptions. Recent preliminary results confirm this for the Constraint Satisfaction Problem (CSP), an important problem with applications for instance in Artificial Intelligence and Operations Research, as well as several well-known special cases, such as the Boolean Satisfiabiliy problem (SAT) and the Graph Homomorphism problem. The goal is to extend the topological intuition above for a larger class of problems than the CSP. We will consider as starting points the quantified versions of SAT (QBF) and a reconfiguration version of SAT. For both problems, complexity classifications based on other techniques are know and we will try to obtain a topological counterpart. We then hope to extend these results beyond the current state-of-the-art for other methods, e.g., the quantified CSP, which is currently a hot topic in computational complexity.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

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

Funding category

Funding further details

Concours allocations