An approximation trichotomy for Boolean #CSP

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone IM_2 from Post's lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions in the complexity class #RH\Pi_1. This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

An approximation trichotomy for Boolean #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 An approximation trichotomy for Boolean #CSP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An approximation trichotomy for Boolean #CSP will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-456203

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.