Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
<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∆(&a...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2020
|