MVLSC HomeIssue Contents

Galois Correspondence for Counting Quantifiers
Andrei A. Bulatov and Amir Hedayaty

We introduce a new type of closure operator on the set of relations, max-implementation, and its weaker analog, max-quantification. Then we show that approximation preserving reductions between counting constraint satisfaction problems (CSPs) are preserved by these two types of closure operators. Together with some previous results this means that the approximation complexity of counting CSPs is determined by partial co-clones of relations that are additionally closed under these new types of closure operators. Galois correspondences of various kind have proved to be quite helpful in the study of the complexity of the CSP. While we were unable to identify a Galois correspondence for partial co-clones closed under max-implementation and max-quantification, we obtain such results for slightly different type of closure operators, k-existential quantification. This type of quantifiers are known as counting quantifiers in model theory, and often used to enhance first order logic languages. We characterize partial co-clones of relations closed under k-existential quantification as sets of relations invariant under a set of partial functions that satisfy the condition of k-subset surjectivity. This is an extended version of [A.Bulatov and A.Hedayaty. Counting quantifiers, subset surjective functions, and counting CSPs. ISMVL 2012, p. 331–336.]

Keywords: Counting constraint satisfaction problem, approximation, co-clones, Galois correspondence

Full Text (IP)