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.

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.

The conference version: pdf

A preprint of the journal version: pdf

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.