|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems | | Tomoyuki Yamakami
; | | Date: |
2 Jul 2010 | | Abstract: | Constraint satisfaction problems (or CSPs) have been extensively studied in
AI, database theory, graph theory, etc. From an approximation viewpoint, it has
been important to approximate the total number of assignments that satisfy all
given Boolean constraints. There is a trichotomy theorem for such approximate
counting for (non-weighted) Boolean CSPs; namely, all such counting problems
are neatly classified into three categories under polynomial-time
approximation-preserving reductions [Dyer, Goldberg, and Jerrum, 2010]. We
extend this result to approximate counting for complex-weighted Boolean CSPs,
provided that all arity-1 constraints are freely available to use. This makes a
significant progress in the quest for the approximation classification of all
counting Boolean CSPs in the most general form. To deal with complex weights,
we employ proof techniques along the line of solving Holant problems [Valiant,
2002, 2008]. Our result also gives an approximation version of the dichotomy
theorem of the complexity of exact counting for such complex-weighted Boolean
CSPs [Cai, Lu, and Xia, 2009]. | | Source: | arXiv, 1007.0391 | | 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