On the Complexity of #CSP

Bulatov (2008) has given a dichotomy for the counting constraint satisfaction problem, #CSP. A problem from #CSP is characterized by a constraint language Gamma, which is a fixed, finite set of relations over a finite domain. An instance of the problem uses these relations to constrain the values taken by a finite set of variables. Bulatov showed that, for any fixed Gamma, the problem of counting the satisfying assignments of instances of any problem from #CSP is either in polynomial time (FP) or #P-complete, according on the structure of the constraint language Gamma. His proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field. We give an elementary proof of Bulatov's dichotomy, based on succinct representations, which we call frames, of a class of highly structured relations, which we call strongly rectangular. We show that these are precisely the relations that are invariant under a Mal'tsev polymorphism. En route, we give a simplification of a decision algorithm for strongly rectangular constraint :languages due to Bulatov and Dalmau (2006). Out proof uses no universal algebra, except for the straightforward concept of the Mal'tsev polymorphism and is accessible to readers with little background in #CSP.