Algorithmique et complexité des problèmes de satisfaction de contraintes (24h, 3 ECTS)
Responsable : Miki Hermann (LIX, École Polytechnique)
Intervenants du cours 2009-2010 :
Manuel Bodirsky (12h)
Miki Hermann (12h)
Motivations et objectifs du cours
Les problèmes de satisfaction de contraintes (CSP, Constraint Satisfaction Problems en anglais) sont apparus au milieu des
années 1970, quand les chercheurs ont reconnu leur importance après la
publication initiale de Montanari, et ils connaissent un véritable
boom depuis la fin des années 1990. Cet essor de la problématique des
CSP se manifeste par la multitude de contributions aux conférences en
informatique fondamentale , une conférence spécialement dédiée à la
problématique des CSP, des publications dans les revues d'informatique
théorique, une revue spécialement dédiée à la problématique des
contraintes, ainsi que de plusieurs livres et monographies. La
popularité des CSP est due au fait que ce formalisme permet de définir
un cadre général pour aborder différents problèmes algorithmiques de
façon uniforme; il permet aussi de développer des algorithmes
universellement applicables dans tous les domaines de l'informatique,
et une analyse algorithmique efficace et élégante. Les CSP trouvent un
impact et des applications dans presque toutes les parties de
l'informatique. Ce sont, par exemple, la programmation par contraintes
(voir les applications ILOG), la théorie de complexité, la
bioinformatique, la théorie et applications des bases de données, en
particulier la fouille de données, l'optimisation de requêtes,
l'intégration de données; la vérification de logiciels, la
cryptographie, la sécurité des protocoles de communication, la
recherche opérationnelle, le raisonnement en logiques non-monotones,
l'intelligence artificielle, pour n'en citer que quelques unes. Il est
donc évident que la recherche en CSP prend une position clé en
informatique.
La recherche sur les CSP regroupe des méthodes issues ou utilisées en
combinatoire et en théorie des graphes, en théorie des modèles, en
algèbre universelle et en théorie de complexité. Pouvoir travailler
dans ce domaine demande donc une grande connaissance et culture des
méthodes mathématiques et informatiques.
Les étudiants, après avoir suivi ce cours, auront une vue globale de
CSP, de leur importance, leurs applications, les algorithmes
sous-jacents et de leur complexité.
Plan du cours
La première partie comporte 4 séances de 3 heures. La deuxième partie 4 séances de 3 heures.
La première partie du cours sera consacrée à la théorie de complexité
des CSP, en s'appuyant sur les ouvrages (Pippenger 1997), (Hell et
Nesetril 2004), (Creignou, Khanna et Sudan 2001) et les articles
(Böhler et al. 2003), (Böhler et al. 2004), (Schaefer 1978),
(Jeavons, Cohen et Gyssens 1997), (Creignou et Hermann 1996). Il
s'agit de la partie que Miki Hermann a déjà enseigné au MPRI dans le
cadre du cours sur les contraintes et optimisation (cours assuré par
Baptiste, Bampis et Hermann) pendant l'année universitaire 2004-2005.
L'analyse des problèmes decomplexité des CSP est basée sur la partie
de l'algèbre universelle utilisant la correspondance de Galois et
traitant les clones et les co-clones. Nous allons donc présenter les
CSP en forme des contraintes basées sur les ensembles finis de
relations S (co-clones) fermés par rapport aux ensembles de
fonctions (clones) appelés les polymorphismes de S. Ces deux
ensembles sont toujours fermés par rapport à la composition, ce qui
nous permet d'établir une caractérisation exacte des contraintes par
fonctions de fermeture. Ainsi on obtient des sous-classes des CSP
ayant toujours la même complexité, permettant de distinguer entre les
classes polynomiales et NP-complètes. Nous allons présenter les
outils pour reconnaitre les cas polynomiaux, ainsi que les algorithmes
permettant de trouver efficaement la réponse pour ces cas.
Le cours commencera par une brève motivation d'utilisation des CSP
avec des exemples incluant le problème d'affectation de fréquences ou
la correction d'un processeur Intel, arrivant ainsi à expliquer la
nécessité et l'utilité du cours. Après quelques définitions
indispensables, introduisant les notions du domaine, de la relation,
de la contrainte et sa satisfaction, aboutissant finalement à la
définition principale du CSP, nous allons présenter quelques exemples
concrets des CSP, comme all-different et 3-coloriage. Nous allons
expliquer comment il faut paramétrer des CSP par un langage de
contraintes S composé par un ensemble de relations, car selon ce
paramètre le CSP peut être polynomial, NP-complet, ou peu-être entre
les deux.
Nous allons aborder les CSP booléens de façon détaillée. Dans ce
cadre, nous allons montrer comment il faut comprendre le problème de
satisfaisabilité SAT comme un CSP. Ensuite, nous allons montrer
comment aboutir à des problèmes de satisfaction spécifiques, comme
3SAT, 2SAT, POSITIVE 1-IN-3 SAT, NOT-ALL-EQUAL 3SAT, HORNSAT, en
modulant le langage de contraintes S. Ainsi, nous pouvons maintenant
poser des questions sur l'équivalence des CSP avec différentes
langages de contraintes, sans pour l'intant être capable de répondre à
cette question. Pour y arriver, nous allons d'abord montrer comment
construire une formula F à partir d'une relation R, telle que
l'ensemble de ses modèles sol(F) soit égal à R. Ensuite, nous allons
aborder la satisfaisabilité des formules particulières en forme
normale conjonctive, notamment Horn (les clauses avec au plus un
littéral positif), dual Horn (au plus un littéral négatif),
bijonctives (clauses d'au plus deux littéraux) et affines (systèmes
d'équations sur l'anneau booléen). Nous allons développer des
algorithmes polynomiaux pour décider la satisfaisabilité de ces
formules. En effet, ces quatre cas spéciaux représentent les seules
classes de formules avec la satisfaisabilité polynomiale.
Nous revenons alors aux relations qui représentent les ensembles de
modèles des contraintes correspondantes et nous allons montrer comment
nous pouvons créer des nouvelles constraintes à partir d'un ensemble
de contraintes existantes, appelé aussi l'implantation de nouvelles
contraintes, par conjonctions, quantification existentielle,
permutation de variables et diagonalisation. Au niveau de relations,
ces opérations correspondent respectivement au produit cartésien, à la
projection, à la permutation de coordonnées, et à la section (une
opération bien connue en théorie des codes). Ces opération sont à la
base de la production des co-clones, c.-à-d. des ensembles cl(S) de
toutes les relations constructibles à partir du langage de contraintes
S. Ceci nous permet maintenant de formuler les théorèmes sur les
reductions entre les CSP paramétrés par deux langages de contraintes
S1 et S2, qui satisfont la relation d'inclusion S1 dans S2. Nous
allons maintenant montrer comment formuler des problèmes de
satisfaisabilité Horn, dual Horn, bijonctive et affines en tant que
CSP avec des langages de contraintes spécifiques. Nous y ajoutons des
langages 0-valides et 1-valides pour compléter les langages de
contraintes donnant lieu aux CSP polynomiaux.
Nous allons procéder par montrer les propriétés de fermeture des
relations Horn, dual Horn, bijonctives, affines, 0- et 1-valides,
ainsi que complémentives par rapport aux fonctions booléennes
particulières. Ceci nous amèmes par généralisation à la notion de
polymorphisme. Nous allons montrer comment utiliser les ensembles clos
de polynomorphismes, aussi appelés de clones, pour caractériser les
enembles de relations et des co-clones. En effet, les clones sont des
ensembles de fontions qui contiennent toutes les projections est sont
clos par composition. Les clones forment un treills ordonné par
inclusion - le fameau treillis de Post. Post a également prouvé que
chaque clone booléen possède une base finie, ce qui nous permet de
caractériser effectivement nos langages de contraintes S. Nous allons
aborder la notion de correspondance de Galois, d'abord en général,
puis appliquée aux clones et co-clones. Cette dernière nous
finalement permet de caractériser totalement la complexité des CSP
pour tout langage booléen de contrainte S, arrivant au fameaux thórème
dichotomique de Schaefer classant des CSP booléens en polynomiaux et
NP-complets. Il faut noter qu'il n'existe pas des CSP flottants entre
les classes P des problèmes de décision polynomiaux et les problèmes
NP-complets, à condition que P est différent de NP, malgré le théorème de Ladner.
Nous allons aussi brièvement aborder les problèmes de comptage,
d'approximation, de la satisfaisabilité unique, de la satisfaisabilité
quantifiée, de l'équivalence et l'isomorphisme, la satisfaisabilité
optimale, les problèmes liés aux bases de données, tous en relation
avec les CSP. Nous allons également aborder des problèmes qui ne
peuvent pas être résolus par la méthode algébrique basée sur la
correspondance de Galois, comme la circonscription ou l'inférence
minimale, car ces problèmes ne sont pas clos par la quantification
existentielle.
Dans la deuxième partie du cours nous allons appliquer les concepts et
techniques du premier partie aux problèmes de satisfaction de
contraintes sur les domaines infinis. Cet approche nous permet de
considérera pr exemple les problèmes en raisonnement spacial et
temporel, en reconstruction phylogénique et les problèmes de calcul en
algèbre dans un cadre uniforme. Nous allons nous focaliser
particulièrement sur les résultats algorithmiques. Par exemple, nous
revisitons les technique de consistance locale et nous introduisons en
CSP des algorithmes de graphes efficaces lesquels n'étaient pas
applicables aux CSP sur les domaines finis. Cette deuxième partie sera
partiellement basée sur un cours du second enseignant préparé en
collaboration avec Hubie Chen pour le European Summer School for Logic, Language and Information en 2007.
Planning des séances
Selon le planning du MPRI.
Plus d'information concernant ce cours et sont planning est disponible sur les pages web de Miki Hermann et Manuel Bodirsky .
Planning de l'examen
L'examen du cours aura lieu le 10 février 2010 de 8h45 à 11h45 dans la salle 8B01 à Chevaleret.
Langues du cours :
Le cours sera a priori en français.
Cependant, s'il est suivi par des étudiants non francophones et en accord avec l'ensemble des étudiants qui le suivent, ce cours pourra aussi être en anglais.
Le sujet d'examen sera en français et en anglais.
Les étudiants seront autorisés à rédiger leur examen en français ou anglais.
Supports de cours :
Les transparents du cours seront disponibles au fur et à mesure sur la page web MPRI C-2-31-1.
Pré-requis
Connaissances de base en complexité, en algorithmique et en algèbre.
Cours liés
Optimisation 2-24-1, Programmation par contraintes 2-4-1.
Bibliographie
E. Böhler, N. Creignou, S. Reith, and H. Vollmer. Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. SIGACT News, Complexity Theory Column 42, 34(4):38-52, 2003.
E. Böhler, N. Creignou, S. Reith, and H. Vollmer. Playing with Boolean blocks, part II: Constraint satisfaction problems. SIGACT News, Complexity Theory Column 43, 35(1):22-35, 2004.
E. Böhler, S. Reith, H. Schnoor, and H. Vollmer. Bases for Boolean co-clones. Information Processing Letters, 96(2):59-66, 2005.
N. Creignou and M. Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125(1) :1-12, 1996.
N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (PA), 2001.
P. Hell and J. Nesetril. Graphs and Homomorphisms. Oxford University Press, 2004.
P. Jeavons, D. Cohen, and M. Gyssens. Closure properties of constraints. Journal of the ACM, 44(4):527-548, 1997.
N. Pippenger. Theories of Computability. Cambridge University Press, Cambridge, 1997.
T. J. Schaefer. The complexity of satisfiability problems. In Proceedings 10th Symposium on Theory of Computing (STOC'78), San Diego (California, USA), pages 216-226, 1978.
