Dagstuhl Seminar 06401
Complexity of Constraints
( Oct 01 – Oct 06, 2006 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/06401
Organizers
- Nadia Creignou (University of Marseille, FR)
- Phokion G. Kolaitis (IBM Almaden Center & UC Santa Cruz, US)
- Heribert Vollmer (Leibniz Universität Hannover, DE)
Contact
Impacts
- Complexity of constraints : an overview of current research themes - Creignou, Nadia; Kolaitis, Phokion G.; Vollmer, Heribert - Berlin : Springer, 2008. - 319 S. - (Lecture notes in computer science : state-of-the-art survey ; 5250). ISBN: 978-3-540-92799-0 / 3-540-92799-9. DOI: 10.1007/978-3-540-92800-3.
- Symmetric Datalog and Constraint Satisfaction Problems in Logspace : article : pp. 193-202 : 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007) - Laszlo Egri ; Benoit Larose ; Pascal Tesson - Los Alamitos : IEEE, 2007. - pp. 193-202.
- Universal algebra and hardness results for constraint satisfaction problems : article : pp. 1629-1647 - Larose, Benoit; Tesson, Pascal - Amsterdam : Elsevier, 2009 - (Theoretical computer science : 410. 2009, 18 : pp. 1629-1647). DOI: 10.1016/j.tcs.2008.12.048.
In a constraint satisfaction problem, the goal is to find an assignment of values to a given set of variables so that certain specified constraints are satisfied. Constraint satisfaction problems were introduced in the 1970s to model computational problems encountered in picture processing. It was quickly realized, however, that constraint satisfaction gives rise to a powerful general framework in which a wide variety of combinatorial problems can be expressed. As a matter of fact, it has been asserted that "Constraint satisfaction has a unitary theoretical model with myriad practical applications" (A. Mackworth, Foreword to Constraint Processing by Rina Dechter, 2003). Thus, nowadays constraint satisfaction problems (CSPs) are ubiquitous in many different areas of computer science, from artificial intelligence and database systems to circuit design, network optimization, and theory of programming languages. Consequently, it is important to analyze and pinpoint the computational complexity of certain algorithmic tasks related to constraint satisfaction. These include determining if a CSP has a solution (and, if so, finding such a solution), counting the number of solutions of a CSP, enumerating all solutions of a CSP, and finding the biggest number of constraints that can be simultaneously satisfied, if a CSP is unsatisfiable. Complexity-theoretic results about these tasks may have direct impact on, for instance, the design and processing of database query languages, or strategies in data-mining, or the design and implementation of planners.
During the past two decades, an impressive array of diverse techniques from mathematical fields, such as propositional logic, model theory, Boolean function theory, universal algebra and combinatorics, have been used to analyze the computational complexity of algorithmic tasks related to CSPs. Although significant progress has been made on several fronts, some of the central questions remain unsolved so far; perhaps the most prominent of these is to obtain a complete classification of the complexity of CSPs over an arbitrary, but fixed, finite domain. One of the main aims of the Dagstuhl Seminar wass to bring together researchers from all areas of activity in constraint satisfaction, so that they can communicate state-of-the-art advances and embark on a systematic interaction that will enhance the synergy between the different areas.
The organizers felt that the seminar would provide a unique opportunity to focus attention on a number of important research problems in the complexity of constraints, including the following:
- Islands of tractability of uniform CSP
- Complexity classifications for non-uniform CSP
- Quantified Constraint Satisfaction
- Study of complexity classes through the lens of Boolean CSP
- Albert Atserias (UPC - Barcelona, ES) [dblp]
- Régis Barbanchon (Aix-Marseille University, FR)
- Michael Bauland (Leibniz Universität Hannover, DE)
- Manuel Bodirsky (HU Berlin, DE) [dblp]
- Elmar Böhler (Universität Würzburg, DE)
- Ferdinand Börner (Universität Potsdam, DE)
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
- Catarina Alexandra Carvalho (Durham University, GB) [dblp]
- Philippe Chapdelaine (IUT Sénart-Fontainebleau, FR)
- Hubie Chen (UPF - Barcelona, ES) [dblp]
- David Cohen (Royal Holloway University of London, GB) [dblp]
- Nadia Creignou (University of Marseille, FR) [dblp]
- Victor Dalmau (UPF - Barcelona, ES) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Arnaud Durand (University Paris-Diderot, FR) [dblp]
- Martin Grohe (HU Berlin, DE) [dblp]
- Marc Gyssens (Hasselt University - Diepenbeek, BE) [dblp]
- Miki Hermann (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Neil Immerman (University of Massachusetts - Amherst, US) [dblp]
- Dmitry Itsykson (Steklov Institute - St. Petersburg, RU) [dblp]
- Peter Jonsson (Linköping University, SE) [dblp]
- Lefteris M. Kirousis (CTI & University of Patras, GR) [dblp]
- Phokion G. Kolaitis (IBM Almaden Center & UC Santa Cruz, US) [dblp]
- Andrei Krokhin (Durham University, GB) [dblp]
- Oliver Kullmann (Swansea University, GB) [dblp]
- Benoit Larose (Champlain Regional College - St. Lambert, CA) [dblp]
- Florent R. Madelaine (Durham University, GB) [dblp]
- Elitza Maneva (University of California - Berkeley, US) [dblp]
- Joachim Niehren (INRIA - University of Lille 1, FR) [dblp]
- Gustav Nordh (Linköping University, SE)
- Steffen Reith (Universität Würzburg, DE) [dblp]
- Florian Richoux (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Francesco Scarcello (University of Calabria, IT) [dblp]
- Henning Schnoor (Universität Hannover, DE) [dblp]
- Ilka Schnoor (Leibniz Universität Hannover, DE)
- Iain A. Stewart (Durham University, GB) [dblp]
- Stefan Szeider (Durham University, GB) [dblp]
- Pascal Tesson (Laval University - Quebec, CA)
- Matt Valeriote (McMaster University - Hamilton, CA) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
Related Seminars
- Dagstuhl Seminar 09441: The Constraint Satisfaction Problem: Complexity and Approximability (2009-10-25 - 2009-10-30) (Details)
- Dagstuhl Seminar 12451: The Constraint Satisfaction Problem: Complexity and Approximability (2012-11-04 - 2012-11-09) (Details)
- Dagstuhl Seminar 15301: The Constraint Satisfaction Problem: Complexity and Approximability (2015-07-19 - 2015-07-24) (Details)
- Dagstuhl Seminar 18231: The Constraint Satisfaction Problem: Complexity and Approximability (2018-06-03 - 2018-06-08) (Details)
- Dagstuhl Seminar 22201: The Constraint Satisfaction Problem: Complexity and Approximability (2022-05-15 - 2022-05-20) (Details)
- Dagstuhl Seminar 25211: The Constraint Satisfaction Problem: Complexity and Approximability (2025-05-18 - 2025-05-23) (Details)
Classification
- data structures/algorithms/complexity
Keywords
- constraint satisfaction problem
- satisfiability problems
- counting problems
- computational complexity
- Post’s lattice
- Galois correspondence
- universal algebra
- homomorphism problem
- combinatorics.
