The constraint satisfaction problem

The American Institute of Mathematics

The following compilation of participant contributions is only intended as a lead-in to the

AIM workshop “The constraint satisfaction problem.” This material is not for public

distribution.

Corrections and new material are welcomed and can be sent to workshops@aimath.org Version: Tue Mar 18 20:13:25 2008

Table of Contents

A. Participant Contributions . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Allender, Eric

2. Atserias, Albert

3. Baldwin, John

4. Bodirsky, Manuel 5. Bulatov, Andrei

6. Carvalho, Catarina 7. Chen, Hubie

8. Dalmau, Victor

9. Dawar, Anuj

10. Dent, Topaz

11. Feder, Tomas

12. Grohe, Martin

13. Hemaspaandra, Edith

14. Hyndman, Jennifer

15. Jeavons, Peter

16. Kearnes, Keith

17. Kolaitis, Phokion

18. Krokhin, Andrei

19. Larose, Benoit

20. Maneva, Elitza

21. Markovic, Petar

22. Maroti, Miklos

23. McKenzie, Ralph

24. Szendrei, Agnes

25. Valeriote, Matthew

26. Vardi, Moshe

27. Willard, Ross

28. Wood, Japheth

Chapter A: Participant Contributions

A.1 Allender, Eric

I must admit that I have done very little work on constraint satisfaction. I was introduced to the topic by a great series of lectures that Phokion Kolaitis gave in Barbados. That series of talks led me to ask if Schaefer’s dichotomy theorem for poly-time reductions would give rise to a finite number of equivalent CSPs when more restrictive notions of reducibility (such as logspace or AC^{0} reducibility) were considered. It does (as my coauthors and I showed in an MFCS ’05 paper).

I’ve been asked to give a talk surveying subclasses of P – which is a topic about which I’m fairly passionate. There is more information than I could possibly cover in the scope of a survey lecture – so if there are particular mysteries about the subclasses of P that you’d like me to unveil for you, please let me know ahead of time.

Although I have not done a great deal of work on CSPs, I do find the topic to be very interesting, and I look forward to learning more about what is going on in the field.

A.2 Atserias, Albert

I am interested in the width-hierarchy problem for constraint satisfaction problems. Are there finite constraint languages with at most binary (or at most ternary) relations that can be solved by some bounded width but not by width three (or four)? I would be interested in getting candidates on which to test the methods for proving lower bounds on refutation complexity of random instances, and understand where they fail when they do. A related question is of course the bounded width conjecture about omitting types 1 and 2. A different direction of my interest is that of studying other algorithmic methods that are potentially stronger than bounded width, such as bounded Sherali-Adams rank in mathematical programming, or logics with counting in descriptive complexity.

A.3 Baldwin, John

I have heard several talks on this problem and was intrigued by the connections with logic and universal algebra. I have written about finite model theory, Malcev Conditions, constructions of varieties involving definability conditions on congruences. These all seem relevant but I would appreciate it if several relevant papers were posted on the AIM site.

A.4 Bodirsky, Manuel

Can we apply the universal-algebraic approach to constraint satisfaction complexity to study CSP(B) for infinite structures B? What are the conditions on B such that the universal-algebraic approach can be applied? These are guiding questions in my research, and these questions motivate several concrete research projects that I think are promising topics for discussions at the workshop.

• An important class of structures B where the algebraic approach applies is the class of ω-categorical structures. Is there an ω-categorical structure B such that CSP(B) is in NP, but neither NP-complete nor in P? If the dichotomy conjecture is false for finite structures B, it might be an interesting first step to refute it for ω-categorical structures first!

• Can we characterize all those structures B where primitive positive definability is captured by preservation under polymorphisms (ω-categoricity is just a sufficient, but not a necessary condition)?

• Classify the constraint satisfaction problems for all structures with a first-order definition in (ℂ, +, ∗), i.e., the complex numbers with addition and multiplication (these structures are not ω-categorical, but the algebraic approach looks promising to study their CSP). Progress in this direction could create interesting links with algebra (not just universal algebra) and model theory.

A.5 Bulatov, Andrei

A number of new algebraic properties, identities, types of algebras have been identified when studying CSPs. At this workshop we could make some group effort to put these new concepts into a wider algebraic context. It would also be quite useful to strengthen the links between logic and algebra that start to appear now through logic and algebraic characterizations of complexity classes.

Several specific problems to work on:

1. Study idempotent algebras that generate congruence singular varieties. Such algebras play a central role in the complexity of counting problems. All of them are Mal’tsev, and it is likely that they have interesting and non-trivial properties.

2. Bulatov introduced colored graphs of (idempotent) algebras and proved that the connectivity of such graphs and omitting edges of the affine type (+connectivity) is equivalent to omitting type 1, and types 1,2, respectively. Are there any other connections to the studied properties of algebras?

3. Search for complexity classes such that problems complete in those classes are representable as CSP(Γ), CSP(A) for some constraint language Γ or and algebra A. Are there any properties except for dualities responsible for the complexity of a problem?

A.6 Carvalho, Catarina

I am generally interested in applications of Universal Algebra to the Constraint Satisfaction Problem, and in particular to problems concerning Dualities for Constraint Satisfaction Problems. Some of the problems I would like to see discussed at this workshop include the existence (and formulation) of an algebraic characterization of path and pathwidth dualities (e.g. an equivalent notion to that of relational width). It would also be interesting to have a complete list of which polymorphisms imply bounded treewidth and bounded pathwidth dualities.

A.7 Chen, Hubie

My main interests are in classifying the complexity of the CSP and the QCSP, and associated universal algebra. I have worked on the complexity of QCSP over finite templates, and also on the complexity of CSP and QCSP over infinite templates. I look forward to participating in this workshop and would be particularly interested in taking part in research that aims to extend the boundary of currently known polynomial-time tractable problems.

A.8 Dalmau, Victor

I am very interested in the constraint satisfaction problem and its connection with universal algebra. In the last couple of years, I have been doing some work on the direction of placing some problems inside Datalog and some of its variants which I would be most interested to extend. In particular (with A. Krokhin) we proved that majority implies linear datalog (properly speaking that if Γ is a set of relations invarinat under a majority operation then the complement of CSP(Γ) is definable in linear datalog). I would be most interested in see whether this extends to arbibrary nufs. Also (with C. Carvalho, P. Markovic and M. Maroti) we showed that CD(4) implies Datalog which I would like to extend to higher number of Jónsson terms. Another recent result (with B. Larose) that I would like to extend shows that Datalog plus invariance under Mal’tsev implies Symmetric Datalog. I would like to see up to which extend the condition “invariance under Mal’tsev” can be weakened. Besides this I am interested in many of the aspects of the CSP.

A.9 Dawar, Anuj

I am interested in whether one can give a logical characterisation of the tractable constraint satisfaction problems. We have shown that there are tractable CSPs that cannot be expressed even in fixed-point logic with counting. Is there a natural logical formalism in which all tractable CSPs can be expressed?

A.10 Dent, Topaz

I am a graduate student in mathematics at the University of Colorado at Boulder, my advisor is Dr. Agnes Szendrei. For my dissertation I am considering algebraic aspects of the constraint satisfaction problem. In particular, I am interested in using clone theory to find new classes of finite idempotent algebras for which the CSP is tractable. At this workshop I look forward to hearing about the current questions surrounding the constraint satisfaction problem. I would like to hear more regarding the current methods that are being used to address these questions, such as the existence of certain terms in the clone of the algebra and particularly useful algorithms for proving tractability.

A.11 Feder, Tomas

I have some algebraic results in the area of quantified constraints.

Here are three open problems on algebras and CSP.

(1) Bulatov showed that list constraints (or conservative constraints) are polynomial or NP-complete. Feder and Hell showed that this classification still holds if not all lists are required, only lists of size at most three and optionally other lists. The obvious question is the case where only the lists of size at most three and optionally other lists are required. If all pairs were generalized-majority-minority or all pairs were commutative-conservative this is easy to show from existing results, but when all three kinds of pairs occur the problem remains open.

(2) Problems with generalized-majority-minority have a polynomial number of generators and are thus unlikely to be P-hard. The obvious question is whether all other problems are P-hard.

(3) Feder showed that a general subgroup problem can be extended to a near subgroup problem and remain Maltsev, while a non-near-subgroup extension is NP-complete by Feder and Vardi. The obvious question is whether when we start with the general case of a Maltsev problem and extend it to a non-Maltsev problem it becomes NP-complete. The same can be asked more generally for extending a gmm to a non-gmm giving NP-completeness.

A.12 Grohe, Martin

My interest in CSP has mostly been on structural restrictions (sometimes called nonuniform CSP) and on counting problems related to CSP, such as the evaluation of the partition functions of certain models of statistical physics. Our results on the complexity of such functions also build on algebraic techniques, but not so much on universal algebra, but rather the classical textbook algebra, like quadratic forms over finite fields. I wonder if these techniques can also be useful in the context of the decision problem; it is one of my goals in this workshop to find out.

As for more clearly defined open problems, I’m interested in the width hierarchy question (see A. Atserias’ contribution) and the question for a logical characterisation of the tractable CSPs (see A. Dawar’s contribution).

A.13 Hemaspaandra, Edith

I am interested in the complexity of logics in general, and in particular in obtaining dichotomy theorems for problems related to Boolean constraint satisfaction.

A.14 Hyndman, Jennifer

This semester I am supervising a seminar on CSP which one student is taking as a fourth year computer science course. I am hoping that the student will work on this area as a Master’s student so I am looking for problems that would be appropriate for him.

In the articles posted on the website for this conference the formulation of two of the conjectures that are appealing to me are:

1) A finite idempotent algebra A is NP-complete if it has a nontrivial factor B all of whose operations are projections. Otherwise it is tractable.

2) A finite idempotent algebra A is tractable if and only if A has a weak near-unanimity term.

A.15 Jeavons, Peter

The link between the complexity of the CSP with a restricted target structure and the polymorphisms of that target structure has generated a lot of interesting algebraic investigations, many of which are still ongoing. However, not much of this algebraic work has yet been translated back into computational or algorithmic insights, and I think this is one of the challenges of work in this area that we shouldn’t lose sight of.

I’d also like to explore the potential for other links between various forms of constraint satisfaction and algebra. For example, many combinatorial optimisation problems can be expressed using some form of “soft constraints” where tuples are assigned cost values, rather than simply allowed or forbidden. Somewhat surprisingly, the complexity of such problems can be characterised by algebraic properties of the cost functions which generalise the idea of polymorphisms (they can be seen as weighted lists of finite functions). In other words, there is a more general Galois connection that links sets of cost functions to “generalised polymorphisms” - see An algebraic characterisation of complexity for valued constraints, Cohen, Cooper, Jeavons Lecture Notes in Computer Science 4204, (2006), pp. 107-121 . I’d like to know how to treat these “generalised polymorphisms” algebraically, and whether there is any existing structural theory for such objects as there is with clones.

Finally, there seems to be an unfortunate gulf between the work done on tractable target structures (sometimes called tractable constraint languages) and work on identifying tractable source structures. The former has mainly involved algebraic and logical characterisations, whereas the latter has used graph and hypergraph theory. Are there interesting connections? What tools can we use to tackle the “uniform” case where both source and target are specified as part of the input?

A.16 Kearnes, Keith

I am generally interested in algebra, model theory and combinatorics, and particularly interested in the structure of finite algebras. I would like to understand which idempotent Maltsev conditions arise naturally in algebra, how these conditions restrict the structure of relational clones, and what structure theorems can be proved from weak idempotent Maltsev conditions. It seems that the investigation of the Feder-Vardi Dichotomy Conjecture will advance our understanding of these questions. During the workshop I would be most interested in collaborating to establish this conjecture.

A.17 Kolaitis, Phokion

I am primarily interested in the connections between constraint satisfaction and mathematical logic. I look forward to participating in problem sessions during the workshop that will be devoted to advancing our understanding of these connections. The main goal is to make progress towards resolving some of the many open problems about the logical aspects of the constraint satisfaction problem. Here are three such problems.

Dichotomy Conjecture for the Descriptive Complexity of CSP: For every constraint language Γ, either CSP(Γ) is definable in Datalog or CSP(Γ) is not definable in the infinitary logic C_{∞ω}^{ω}, a powerful finite-variable infinitary logic with counting quantifiers.

The Hierarchy Problem for Datalog-definable CSPs: Prove or disprove that for every k ≥ 4, there is a constraint language Γ_{k} such that CSP(Γ_{k}) is definable in k-Datalog, but not in (k − 1)-Datalog.

Datalog vs. Least Fixed-Point Logic for CSP: Is there a constraint language Γ such that CSP(Γ) is definable in least fixed point logic LFP (hence, it is tractable), but not definable in Datalog?

A.18 Krokhin, Andrei

I’m interested in all research directions mentioned on the workshop’s webpage: computational complexity classifications for CSPs with restricted constraint languages, classifications with respect to definability in Datalog and its fragments, the link of those problems with universal-algebraic conditions, the Datalog hierarchy problem. It seems that currently the biggest challenge is to find a way to extract, from algebraic conditions, structural information that can be used to design algorithms or to prove definabiltiy in various fragments of Datalog (say, through dualities or pebble games).

A.19 Larose, Benoit

My present research on the CSP focuses mainly on verifying the lower complexity dichotomy conjectures in special cases such as the list-homomorphism problem for structures with a single binary relation. More precisely, I’d like to characterise those structures for which (a) the (complement of the) CSP is in (linear, symmetric) Datalog and

(b) the associated algebra generates a variety omitting types {1, 2} ({1, 2, 5}, {1, 2, 4, 5}).

A.20 Maneva, Elitza

I am interested in identifying structural properties of relations using the properties of the congruence lattices of their algebras. An example is the study of the structure of the solution space of CSPs with respect to the graph obtained by placing an edge between satisfying assignments at Hamming distance 1. Notice that this edge relation is the union of n congruences, thus it has several natural generalizations.

The Boolean case was studied in a paper with Parikshit Gopalan, Phokion Kolatis, and Christos Papadimitriou. There we showed that for the tractable CSPs if there is a path between two solutions, then there is a path of length at most 2n. On the other hand for 3-SAT and most other NP-hard CSPs (ones we call non-tight) there are formulas where the shortest path between some pair of assignments is exponential in n. (For a more liberal set of congruences (not just Hamming distance 1) one can construct an exponential length shortest path in any Boolean NP-hard CSP.)

Secondly, I wonder if there is an approach to use directly the properties of congruences to get tractability results, rather than using the corresponding polymorphisms.

And finally, I would be interested in seeing how researchers in universal algebra play with concrete algebras and their corresponding CSPs, congruences, polymorphisms, etc. Perhaps we could learn about software implementations like the Universal Algebra Calculator.

A.21 Markovic, Petar

My interest in CSP is in the avenue of attack towards the main Dichotomy Conjecture by T. Feder and M. Y. Vardi via universal-algebraic methods in conjunction with logic and graph theory. There are two specific problems which I would like to discuss with other participants:

The first one is involving the Mal’cev conditions which imply tractability. In particular, attempting to prove that when the constraint language is invariant under a sequence of Jónsson terms (i.e. when the dual algebra is generating a congruence-distributive variety), then this constraint language has bounded width. I strongly believe that if one was able to prove this only in the shortest unknown case of the Jónsson sequence, when the dual algebra is A = ⟨A; p_{1}, p_{2}, p_{3}⟩, satisfying the identities

\begin{aligned}p_{i}(x, y, x) & ≈ & x \\ p_{1}(x, y, y) & ≈ & x \\ p_{i}(x, x, y) & ≈ & p_{2}(x, x, y) \\ p_{2}(x, y, y) & ≈ & p_{3}(x, y, y) \\ p_{3}(x, x, y) & ≈ & y \end{aligned}

then one would be very close to proving it for any Jónsson sequence. I base this belief on the recent result obtained in collaboration with C. Carvalho, V. Dalmau and M. Maróti and the way it fails to generalize.

The second problem involves generalizations of the excellent result by L. Barto, M. Kozik and T. Niven which states that if a finite directed graph G has no sources nor sinks (i.e the in-degree and the out-degree of each vertex is positive), then CSP (G) exhibits a dichotomy. The tractable graphs are precisely the ones in which each weakly connected component can be retracted to a circle (directed cycle with no diagonals) and the rest are NP-complete. In a recent collaboration with R. McKenzie, we were able to generalize this result slightly, but the methods we discovered might be useful to (at most) graphs with no sinks, though that would be extremely difficult. I would like to report on our results and see if the participants are interested in attempts to extend them.

A.22 Maroti, Miklos

1) Study of universal algebraic problems inspired by research on the CSP but interesting on their own, e.g. is it true that every finite algebra in a congruence meet semidistributive variety has a cyclic term?

2) Prove the tractability of finite algebras with a weak near-unanimity term satisfying t(y, x, ..., x) ∈ {x, y} for all x, y. This would be a generalization of the conservative algebra result of A. Bulatov, and the generalized majority-minority term result of V. Dalmau.

3) Describe the structure of core oriented trees that have a weak near-unanimity polymorphism. Is it true that all such trees have bounded width?

A.23 McKenzie, Ralph

I am fascinated by the possible application of finite universal algebra to the dichotomy conjecture for constraint satisfaction problems, and equally fascinated by the reverse application of perspectives and questions generated by CSP considerations to sharpening our understanding of finite algebras. Algebraic questions arising from CSP considerations have already generated some very surprising results—for instance the characterization of a most general Taylor term as a weak near-unanimity term, and the development of the general theory of algebras with few subpowers (which in turn yielded new results in the CSP).

The relevance of finite universal algebra to CSP has been validated repeatedly, most recently and spectacularly in the proof by L. Barto, M. Kozik and T. Niven that for a finite digraph G without sources or sinks, CSP(G) is NP-complete unless G is a disjoint sum of circles (in which case CSP(G) is polynomial-time). I have been working for the past five months with P. Markovic attempting to extend this result to wider classes of graphs. Our results, thus far, are very modest; but the efforts have been very stimulating and seem to have given me a visceral appreciation of the difficulty of the dichotomy conjecture.

With R. Willard, I would support group attacks during the workshop, attempting to prove tractability of CSP(A) for some well-defined classes of finite idempotent algebras which we suspect must be tractable, for example, those with relatively short sequences of Jónsson operations.

A.24 Szendrei, Agnes

My background is in algebra, primarily in the structure theory of finite algebras and in clone theory. Therefore the topic within CSP that is closest to my research interests is the algebraic approach to the Feder-Vardi Dichotomy Conjecture. I am looking forward to joining a group attack, as suggested by R. Willard, attempting to get new tractability results for finite idempotent algebras. I would also like to learn more about algorithmic issues and the logical aspects of CSP during the workshop.

A.25 Valeriote, Matthew

I’m interested in investigating the (conjectured) connections between the complexity of the class CSP(G), for G a constraint language, and the properties of the associated finite algebra A(G) that can be expressed in the language of tame congruence theory. The conjectures of Bulatov-Jeavons-Krokhin, Larose-Tesson, and Larose-Zadori can all be formulated in these terms and have been verified in (very) special cases.

Another problem that I’d like to work on is that of determining if the width hierarchy is infinite or not. An earlier attempt to establish this using weak near-unanimity terms was not successful, but there may be other natural algebraic features of a constraint language that can be correlated with the width of the language.

A.26 Vardi, Moshe

The Feder-Vardi conjecture started as a problem that intrigued two people. It has evolved into a mini research area with fascinating connections to logic and universal algebra. The former was studied explicitly in the 1993 paper, but the latter was just hinted at, with some discussion of closure functions. The intense interest of universal algebraists in this problem seems to me just short of miraculous. There is a sense that universal-algebra techniques are close to resolving the dichotomy conjecture. I’d like to see that happens.

A.27 Willard, Ross

I am primarily interested in the attack on the Feder-Vardi Dichotomy conjecture via universal algebraic methods; hence I am also interested in the (Algebraic) Tractability conjecture.

I have recently been particularly interested in the conjecture of Zádori and Larose that a finite idempotent algebra has finite width iff the variety it generates omits types 1 and 2. I am also interested in, though not competent in, the related Datalog conjectures.

An activity that I would strongly support during the week of the AIM workshop would be a group attack attempting to prove tractability for specific examples of finite idempotent algebras which omit type 1 (or types 1 and 2) but which are not yet known to be tractable by current methods.

A.28 Wood, Japheth

As a researcher in Universal Algebra, I have already published computability results. With R. McKenzie, we interpreted the Halting Problem for Turing Machines into finite algebras to show that in general, The Typeset of a Variety is not Computable (R. McKenzie and J. Wood, Int. Jour. of Algebra and Computation 11 (2001) 89-130). Later, I showed in Subtraces and Shadowchains (J. Wood Algebra Universalis 41 (1999) 233–237) that some information about the typeset of a finitely generated variety is computable by inspecting the free algebra on two generators. I am interested in moving from previous results in computability to research in complexity theory.

I am also very interested in coming away from the workshop with open problems that are appropriate for student research. As part of my work at the MAT (masters of arts in teaching) Program at Bard College, I supervise research projects for pre-service math teachers. With another math professor, Bob McGrail, at Bard, we have been working with undergraduate math majors and masters students (from the MAT Program) researching the constraint satisfaction problem as it relates to quandles, a type of algebra that comes from knot theory. Promoting student research in universal algebra will help popularize the field and help improve the undergraduate and masters experience for our students, but depends on being able to offer topics for research.