| 题名: | dichotomy for holant* problems of boolean domain |
| 作者: | Cai Jin-Yi
; Lu Pinyan
; Xia Mingji
|
| 会议文集: | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
|
| 会议名称: | 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
|
| 会议日期: | 23-Jan
|
| 出版日期: | 2011
|
| 会议地点: | San Francisco, CA, United states
|
| 关键词: | Algorithms
; Polynomial approximation
; Theorem proving
|
| 出版地: | United States
|
| 收录类别: | EI
|
| ISBN: | 9780898719932
|
| 部门归属: | (1) University of Wisconsin-Madison, United States; (2) Microsoft Research Asia, China; (3) Institute of Software, Chinese Academy of Sciences, China
|
| 主办者: | ACM Spec. Interest Group. Algorithms Comput. Theory (SIGACT); SIAM Activity Group on Discrete Mathematics
|
| 英文摘要: | 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. |
| 内容类型: | 会议论文
|
| 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.
|
|
|
