| Summary: | <p>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.</p>
|
|---|