Applications of universal algebra and logic to the constraint satisfaction problem

March 31 to April 4, 2008

at the

American Institute of Mathematics, San Jose, California

organized by

Anuj Dawar, Phokion Kolaitis, Benoit Larose, and Matt Valeriote

Original Announcement

This workshop will be devoted to advancing the understanding of the computational complexity of the constraint satisfaction problem using methods and techniques from universal algebra and logic. The intended participants are researchers in computational complexity, universal algebra, and logic. By bringing together researchers from these three areas, progress could be made towards resolving long-standing open problems about the complexity of constraint satisfaction. The most prominent such problem is the Dichotomy Conjecture formulated by Feder and Vardi in 1993, which asserts that, for every constraint language C over an arbitrary finite domain, either the constraint satisfaction problem CSP(C) is in P or it is NP-complete.

The main topics for the workshop are:

While the Feder-Vardi Dichotomy Conjecture has been the main open problem motivating the research in this areas, several other related conjectures and open problems (some of which may be more manageable) have also emerged in recent years. In particular, the workshop will attempt to address the following problems.
  1. Tractability Conjecture: Let C be a constraint language with an idempotent associated algebra A(C). If the variety generated by A(C) omits the unary type, then CSP(C) is in P; otherwise, CSP(C) is NP-complete.

    This conjecture, which has been formulated by Bulatov, Jeavons, and Krokhin, refines the Feder-Vardi Dichotomy Conjecture by suggesting a classification of the complexity of constraint satisfaction in terms of universal algebra.

  2. Definability-in-Datalog Conjecture: Let C be a constraint language with an idempotent associated algebra A(C). Then CSP(C) is definable in Datalog if and only if the variety generated by A(C) omits the unary and affine types.
  3. Dichotomy Conjecture for the Descriptive Complexity of CSP: For every constraint language C, either CSP(C) is definable in Datalog or CSP(C) is not definable in the finite-variable infinitary logic with counting quantifiers.
  4. The Hierarchy Problem for Datalog-definable CSPs: Prove or disprove that for every k > 3, there is a constraint language C(k) such that CSP(C(k)) is definable in k-Datalog, but not in (k-1)-Datalog.
  5. Determine how membership of CSP(C) in the complexity class L and in the complexity class NL (and how completeness of CSP(C) for these classes) corresponds to omitting-types conditions on the associated varieties.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

Papers arising from the workshop:

On the complexity of MM1SNP
by  Manuel Bodirsky, Hubie Chen, and Tomás Feder