Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems

摘要

We study the complexity of #CSPΔ(Γ), which is the problem of counting satisfying assignments to CSP instances with constraints from Γ and whose variables can appear at most Δ times. Our main result shows that: (i) if every function in Γ is affine, then #CSPΔ(Γ) is in FP for all Δ, (ii) otherwise, if every function in Γ is in a class called IM2, then for large Δ, #CSPΔ(Γ) is equivalent under approximation-preserving reductions to the problem of counting independent sets in bipartite graphs, (iii) otherwise, for large Δ, it is NP-hard to approximate #CSPΔ(Γ), even within an exponential factor.