The complexity of approximating conservative counting CSPs
arXiv:1208.1783 · doi:10.1016/j.jcss.2014.06.006
Abstract
We study the complexity of approximately solving the weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, there is a classification known for the case in which the domain of functions in F is Boolean. In this paper, we give a classification for the more general problem where functions in F have an arbitrary finite domain. We define the notions of weak log-modularity and weak log-supermodularity. We show that if F is weakly log-modular, then #CSP(F)is in FP. Otherwise, it is at least as difficult to approximate as #BIS, the problem of counting independent sets in bipartite graphs. #BIS is complete with respect to approximation-preserving reductions for a logically-defined complexity class #RHPi1, and is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, then we show that #CSP(F) is as easy as a (Boolean) log-supermodular weighted #CSP. Otherwise, we show that it is NP-hard to approximate. Finally, we give a full trichotomy for the arity-2 case, where #CSP(F) is in FP, or is #BIS-equivalent, or is equivalent in difficulty to #SAT, the problem of approximately counting the satisfying assignments of a Boolean formula in conjunctive normal form. We also discuss the algorithmic aspects of our classification.
arXiv commentMinor revision
References in corpus (8)
- Approximating the partition function of the ferromagnetic Potts model
- The Complexity of Weighted Boolean #CSP
- The complexity of weighted and unweighted #CSP
- The complexity of conservative valued CSPs
- The expressibility of functions on the Boolean domain, with applications to Counting CSPs
- A Maximal Tractable Class of Soft Constraints
- A Dichotomy Theorem for General Minimum Cost Homomorphism Problem
- Non-negative Weighted #CSPs: An Effective Complexity Dichotomy
Cited by in corpus (9)
- #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
- Approximate counting CSP seen from the other side
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- Functional Clones and Expressibility of Partition Functions
- Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
- Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
- Holant clones and the approximability of conservative holant problems
- A complexity trichotomy for approximately counting list H-colourings
- Hierarchies of Minion Tests for PCSPs through Tensors