The expressibility of functions on the Boolean domain, with applications to Counting CSPs

Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg +2

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using…