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

Full-time Computer Occupations

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