|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems | | Tomoyuki Yamakami
; | | Date: |
6 Mar 2013 | | Abstract: | A unary constraint (on the Boolean domain) is a function from {0,1} to the
set of real numbers. A free use of auxiliary unary constraints given besides
input instances has proven to be useful in establishing a complete
classification of the computational complexity of approximately solving
weighted counting Boolean constraint satisfaction problems (or #CSPs). In
particular, two special "constant" unary constraints are a key to an arity
reduction of arbitrary constraints, necessary for the classification. To
clarify the essential role of auxiliary free unary constraints, we demonstrate
the efficient approximability of the two constant unary constraints by an
arbitrary nonempty set of real-valued constraints. By a direct application of
this approximability result, we construct polynomial-time randomized
approximation-preserving Turing reductions (or AP-reductions) to any given #CSP
composed of symmetric real-valued constraints of arbitrary arities from #CSP(g)
for an appropriate constraint g without any use of extra unary constraints.
Moreover, we can give a precise description of this constraint g. | | Source: | arXiv, 1303.1347 | | 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