Computer Science – Computational Complexity
Scientific paper
2010-07-02
Computer Science
Computational Complexity
A4, 10 point, 25 pages. This second version improves its conference version that appeared in the Proceedings of the 8th Worksh
Scientific paper
Constraint satisfaction problems (or CSPs) have been extensively studied in, for instance, artificial intelligence, database theory, graph theory, and statistical physics. From a practical viewpoint, it is beneficial to approximately solve CSPs. When one tries to approximate the total number of truth assignments that satisfy all Boolean constraints for (unweighted) Boolean CSPs, there is a known trichotomy theorem; namely, all such counting problems are neatly classified into three categories under polynomial-time approximation-preserving reductions. In contrast, we obtain a dichotomy theorem of approximate counting for complex-weighted Boolean CSPs, provided that all complex-valued unary constraints are freely available to use. The expressive power of those unary constraints enables us to prove a stronger, complete classification theorem. This makes a step forward in the quest for the approximation-complexity classification of all counting CSPs. To deal with complex weights, we employ proof techniques of factorization and arity reduction along the line of solving Holant problems. We introduce a novel notion of T-constructibility that naturally induces approximation-preserving reducibility. Our result also gives an approximation analogue of the dichotomy theorem on the complexity of exact counting for complex-weighted Boolean CSPs.
No associations
LandOfFree
Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems 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 Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-727543