Computer Science – Computational Complexity
Scientific paper
2009-07-15
Computer Science
Computational Complexity
22 pages. Full classification now applies to degree bounds of at least 6 (formerly at least 25) but no other significant chang
Scientific paper
The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs.
Dyer Martin
Goldberg Leslie Ann
Jalsenius Markus
Richerby David
No associations
LandOfFree
The Complexity of Approximating Bounded-Degree Boolean \sharp CSP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Approximating Bounded-Degree Boolean \sharp CSP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Approximating Bounded-Degree Boolean \sharp CSP will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-365091