CSP-Complexity is a research project funded by the European Research Council (ERC) as starting grant 257039, ERC-2010-StG_20091028. The hosting institution is the CNRS, via the Laboratoire d'Informatique de l'École Polytechnique (LIX), and the project is part of the Algorithms and Complexity Team.
The complexity of Constraint Satisfaction Problems (CSPs) has become a major common research focus of graph theory, artificial intelligence, and finite model theory. A recently discovered connection between the complexity of CSPs on finite domains to central problems in universal algebra led to additional activity in the area. The goal of this project is to extend the powerful techniques for constraint satisfaction to CSPs with infinite domains. The generalization of CSPs to infinite domains enhances dramatically the range of computational problems that can be analyzed with tools from constraint satisfaction complexity theory. Many problems from areas that have so far seen no interaction with constraint satisfaction complexity theory can be formulated using infinite domains (and not with finite domains), e.g. in phylogenetic reconstruction, temporal and spatial reasoning, computer algebra, and operations research. It turns out that the search for systematic complexity classification in infinite domain constraint satisfaction often leads to fundamental algorithmic results. The generalization of constraint satisfaction to infinite domains poses several mathematical challenges: To make the universal algebraic approach work for infinite domain constraint satisfaction we need fundamental concepts from model theory and results from Ramsey theory. The most important challenges are of an algorithmic nature: finding efficient algorithms for significant constraint languages, but also to understand the class of problems that can be solved by a given algorithm or a given algorithmic technique.
La complexité des problèmes de résolution de contraintes (CSPs) est devenue un important sujet de recherche cumulant la théorie des graphes, l'intelligence artificielle et la théorie des modèles finis. Un lien récemment découvert entre la complexité des CSPs sur les domaines finis et les problèmes centraux en algèbre universelle a mené à une activité nouvelle dans ce secteur. Le but de ce projet est d'étendre les puissantes techniques de résolution des contraintes aux domaines infinis. La généralisation des CSPs aux domaines infinis est importante, car elle augmente nettement la gamme des problèmes algorithmiques qui peuvent être analysés avec les outils consacrés à la complexité de résolution des contraintes. Beaucoup de problèmes, qui pour l'instant n'ont eu aucune interaction avec la théorie de la complexité de résolution de contraintes, ne peuvent être formulés qu'en utilisant des domaines infinis. Il s'agit, par exemple, de raisonnement temporel et spatial, des problèmes de reconstruction phylogénétique, et de recherche opérationnelle. Ceci mènera à de nouveaux résultats algorithmiques, mais également à des résultats systématiques de classification de complexité (ces deux types des résultats s'avèrent intimement liés). La généralisation des CSPs aux domaines infinis soulève plusieurs nouveaux défis mathématiques. Pour pouvoir appliquer les méthodes d'algèbre universelle aux problèmes de résolution des contraintes sur les domaines infinis, nous avons besoin des concepts fondamentaux de la théorie de Ramsey et des résultats de la théorie des modèles. Les défis les plus importants sont d'une nature algorithmique : trouver des algorithmes efficaces pour d'interéressants langages des contraintes, mais également comprendre la classe des problèmes qui peuvent être résolus par un algorithme (ou une technique algorithmique) donné.
The group has a close cooperation with the Equipe de Logique Mathematique of the University Paris 7, in particular with