Logic List Mailing Archive

"Applications of universal algebra and logic to the constraint satisfaction problem", Palo Alto CA (U.S.A.), 31 Mar - 4 Apr 2008

Applications of universal algebra and logic to the constraint satisfaction
problem
http://aimath.org/ARCC/workshops/constraintsatis.html

March 31 to April 4, 2008

at the

American Institute of Mathematics, Palo Alto, California

organized by

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

This workshop, sponsored by AIM and the NSF, 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.

   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.

The workshop will differ from typical conferences in some regards.
Participants will be invited to suggest open problems and questions before
the workshop begins, and these will be posted on the workshop website. These
include specific problems on which there is hope of making some progress
during the workshop, as well as more ambitious problems which may influence
the future activity of the field. Lectures at the workshop will be focused
on familiarizing the participants with the background material leading up to
specific problems, and the schedule will include discussion and parallel
working sessions.

The deadline to apply for support to participate in this workshop has
passed.

For more information email workshops@aimath.org