A clone is a set of functions that is closed under generalized substitution. The set FP of functions being computable deterministically in polynomial time is such a clone. It is well-known that the set of subclones of every clone forms a lattice. We study the lattice below FP, which contains ... more >>>

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the quantified constraint satisfaction problem (QCSP), ... more >>>

We present algebraic conditions on constraint languages \Gamma that ensure the hardness of the constraint satisfaction problem CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP(\Gamma) is not first-order definable then it ... more >>>

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite relational structure H can be expressed as follows: given a relational structure G over the same vocabulary, determine the number of homomorphisms from G to H. In this paper we characterize relational structures H for which #CSP(H) can be solved in ... more >>>