| Title: | dichotomy for holant* problems of boolean domain |
| Author: | Cai Jin-Yi
; Lu Pinyan
; Xia Mingji
|
| Source: | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
|
| Conference Name: | 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
|
| Conference Date: | 23-Jan
|
| Issued Date: | 2011
|
| Conference Place: | San Francisco, CA, United states
|
| Keyword: | Algorithms
; Polynomial approximation
; Theorem proving
|
| Publish Place: | United States
|
| Indexed Type: | EI
|
| ISBN: | 9780898719932
|
| Department: | (1) University of Wisconsin-Madison, United States; (2) Microsoft Research Asia, China; (3) Institute of Software, Chinese Academy of Sciences, China
|
| Sponsorship: | ACM Spec. Interest Group. Algorithms Comput. Theory (SIGACT); SIAM Activity Group on Discrete Mathematics
|
| English Abstract: | Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant* (F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique arid indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (lion-zero) vector whose inner product with itself is zero. |
| Content Type: | 会议论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/14323
|
| Appears in Collections: | 计算机科学国家重点实验室 _会议论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| dichotomy for holant problems of boolean domain.pdf（366KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
Cai Jin-Yi,Lu Pinyan,Xia Mingji. dichotomy for holant* problems of boolean domain[C]. 见:22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. San Francisco, CA, United states. 23-Jan.
|
|
|
