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:
- Constraint satisfaction and universal algebra: Closure properties of
constraints, Mal'cev conditions, tame congruence theory and the local
structure of finite algebras.
- Constraint satisfaction and logic: Conjunctive queries, Datalog,
and finite-variable infinitary logics.
- Connections between universal algebra and logic, and their uses
in delineating the boundary between tractability and intractability
for constraint languages.
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.
- 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.
- 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.
- 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.
- 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.
- 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: