Classification de la complexité des

Les problèmes de satisfaction de contraintes (CSP) fournissent un formalisme permettant de modéliser de nombreux problèmes, dans des domaines très variés comme l’intelligence artificielle ou les bases de données. Une instance d’un CSP consiste en un ensemble de variables sur un domaine D et un ensemble de contraintes, c’est-à -dire de relations sur ces variables restreignant les valeurs qu’elles sont autorisées à prendre, le but étant généralement de vérifier que l’on peut trouver un assignement sur les variables tel qu’aucune relation n’est enfreinte. Dans le cas o๠l’ensemble des relations permettant de construire les contraintes est restreint, on peut parfois obtenir une classification de la complexité. Ainsi, si les seules relations pouvant àªtre utilisées sont booléennes, sur le domaine {0,1}, on sait par le théorème de Schaefer que le problème consistant à décider si un ensemble de contraintes est satisfaisable est soit polynomial, soit NP-complet. Ce résultat de classification est fortement lié au pouvoir d’expression des relations, c’est-à -dire à l’ensemble des relations dont elles peuvent simuler le comportement.

Nous verrons deux approches différentes permettant de mesurer ce pouvoir d’expression. La première est liée aux propriétés de clôture des ensembles de relations et à la correspondance de Galois entre les ensembles clos de relations sur un domaine D et les ensemble clos de fonctions sur D. Dans le cas booléen, cette correspondance permet d’obtenir aisément une classification de la complexité pour certains problèmes. Pour d’autres problèmes, en revanche, une approche constructive plus classique se révèle nécessaire pour obtenir de telles classifications. Nous montrerons des classifications, pour les problèmes du comptage et de la recherche locale, obtenues par ces deux méthodes.