|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems | | Tomoyuki Yamakami
; | | Date: |
27 Sep 2011 | | Abstract: | 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. | | Source: | arXiv, 1109.5789 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER