Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 1 Décembre 2009

Complexité des CSP monotones

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

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr