Applications of universal algebra and logic to the constraint satisfaction problem

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.

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

Plain text announcement or brief announcement.

Go to the American Institute of Mathematics.
Go to the list of upcoming workshops.