The Complexity of #CSP
Authors:
Preprint
Abstract
Bulatov (2008) has given a dichotomy for the counting constraint satisfaction problem (#CSP). A problem from #CSP is characterised by a constraint language, a fixed, finite set of relations over a finite domain. An instance of the problem uses these relations to constrain the variables in a larger set. Bulatov showed that the problem of counting the satisfying assignments of instances of any problem from #CSP is either in polynomial time (FP) or is #P-complete. 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 which 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).Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- A Complexity Dichotomy For Hypergraph Partition Functionscomputational complexity, 2010
- The Complexity of Weighted Boolean #CSPSIAM Journal on Computing, 2009
- The Complexity of the Counting Constraint Satisfaction Problem2008
- Towards a dichotomy theorem for the counting constraint satisfaction problemInformation and Computation, 2007
- A Simple Algorithm for Mal'tsev ConstraintsSIAM Journal on Computing, 2006
- Classifying the Complexity of Constraints Using Finite AlgebrasSIAM Journal on Computing, 2005
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group TheorySIAM Journal on Computing, 1998
- On Monadic NP vs Monadic co-NPInformation and Computation, 1995
- The Complexity of Enumeration and Reliability ProblemsSIAM Journal on Computing, 1979
- Monadic generalized spectraMathematical Logic Quarterly, 1975