Manuel Bodirsky

The Complexity of Equality Constraint Languages

With Jan Kára. Theory of Computing Systems 43(2), 136-158. A conference version of the paper appeared in the proceedings of the International Computer Science Symposium in Russia, CSR06, St.Petersburg, pages 114-126, 2006.

Abstract

We apply the algebraic approach to infinite-valued constraint satisfaction to classify the computational complexity of all constraint satisfaction problems with templates that have a highly transitive automorphism group. A relational structure has such an automorphism group if and only if all the constraint types are Boolean combinations of the equality relation, and we call the corresponding constraint languages equality constraint languages . We show that an equality constraint language is tractable if it admits a constant unary or an injective binary polymorphism, and is NP-complete otherwise.

Download

The conference version: pdf

A preprint of the journal version: pdf

Remarks and Related Papers

An equality constraint language is a relational structure where every relation has a first-order definition over the language that only contains equality. An example of such a structure is the structure over the natural numbers with a single ternary relation containing all triples of elements that have exactly two distinct values. We prove that the constraint satisfaction problem for equality constraint languages is in P, or NP-complete. The corresponding results for the quantified constraint satisfaction problem of equality constraint languages can be found here.

The paper also contains an interesting universal-algebraic result: every locally closed clone on an infinite set that has essential operations and contains all permutations of the domain also contains the constant operation or a binary injective operation. This result about locally closed clones that contain all permutations has been refined in this paper.

---