Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems

Details Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems

2011-09-27

arxiv.org/abs/1109.5789v1

Computer Science

Computational Complexity

A4, 10pt, 23 pages. This is a complete version of the paper that appeared in the Proceedings of the 17th Annual International

Scientific paper

Constraint satisfaction problems have been studied in numerous fields with practical and theoretical interests. In recent years, major breakthroughs have been made in a study of counting constraint satisfaction problems (or #CSPs). In particular, a computational complexity classification of bounded-degree #CSPs has been discovered for all degrees except for two, where the "degree" of an input instance is the maximal number of times that each input variable appears in a given set of constraints. Despite the efforts of recent studies, however, a complexity classification of degree-2 #CSPs has eluded from our understandings. This paper challenges this open problem and gives its partial solution by applying two novel proof techniques--T_{2}-constructibility and parametrized symmetrization--which are specifically designed to handle "arbitrary" constraints under randomized approximation-preserving reductions. We partition entire constraints into four sets and we classify the approximation complexity of all degree-2 #CSPs whose constraints are drawn from two of the four sets into two categories: problems computable in polynomial-time or problems that are at least as hard as #SAT. Our proof exploits a close relationship between complex-weighted degree-2 #CSPs and Holant problems, which are a natural generalization of complex-weighted #CSPs.

Affiliated with

Also associated with

No associations

Rating

Approximation Complexity of Complex-Weighted Degree-Two Counting 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 Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-62110