Florian Richoux (LIX)

Les problèmes de satisfaction de contraintes (CSP) constituent un formalisme permettant de modéliser un grand nombre de problèmes algorithmiques et combinatoires (sur les graphes, bases de données, en intelligence artificielle, …). Le problème CSP est un problème de décision où l’on cherche à savoir si une formule CSP, à savoir une conjonction de contraintes, est satisfaisable. Ce problème est NP-complet en général, mais on connait des sous-problèmes qui sont dans P, par exemple en se limitant à certains ensembles de contraintes que l’on peut utiliser dans une formule CSP. On connait tous les ensembles de contraintes impliquant la polynomialité de notre problème sur les domaines booléens et ternaires, cependant cela reste une question ouverte pour les domaines de cardinalité supérieure. Nous nous intéresserons dans cet exposé à une extension du formalisme CSP, appelé CSP monotone, où la disjonction est autorisée entre les contraintes. Nous présenterons nos résultats déterminant l’ensemble des ensembles de contraintes impliquant la polynomialité de notre problème sur tous domaines de cardinalités finis, mais également et surtout sur les domaines infinis dénombrables ou indénombrables.