TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 06401

Complexity of Constraints

( 01. Oct – 06. Oct, 2006 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/06401

Organisatoren




Summary

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

Teilnehmer
  • 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]

Verwandte Seminare
  • 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)

Klassifikation
  • data structures/algorithms/complexity

Schlagworte
  • constraint satisfaction problem
  • satisfiability problems
  • counting problems
  • computational complexity
  • Post’s lattice
  • Galois correspondence
  • universal algebra
  • homomorphism problem
  • combinatorics.