The expressibility of functions on the boolean domain, with applications to counting CSPs
The expressibility of functions on the boolean domain, with applications to counting CSPs
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 primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational …