Résumé de séminaire

Résumé :

Les problèmes de satisfaction de contraintes sont maintenant étudiés par une communauté théorique qui regroupe des personnes d'horizon assez varié. En effet, ces problèmes peuvent être approchés par des outils algébriques, des outils logiques et des outils combinatoires. La richesse des approches s'explique peut-être par l'ubiquité de ces problèmes: on les retrouve sous différents noms et formes un peu partout, par exemple en bases de données (problème de jointure, inclusion de requêtes existentielles conjonctives), en théorie des graphes (coloriage de graphes) et en "logique" (problème Sat). L'un des problème important est de classifier ces problèmes par leur complexité et en particulier, d'établir la véracité de la conjecture de la dichotomie, à savoir que tout problème de contraintes est soit facile (dans P) soit difficile (NP-complet). Une autre question intéressante est de donner une caractérisation logique de ces problèmes.

Dans l'exposé, je vais donner une introduction aux problèmes de satisfaction de contraintes et présenter des résultats autour de ces deux questions.