Institutional Repository
| dichotomy for holant* problems of boolean domain | |
| Cai Jin-Yi; Lu Pinyan; Xia Mingji | |
| 2011 | |
| Conference Name | 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 |
| Source | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
| Pages | 1714-1728 |
| Conference Date | 23-Jan |
| Conference Place | San Francisco, CA, United states |
| Indexed Type | EI |
| Publish Place | United States |
| ISBN | 9780898719932 |
| Department | (1) University of Wisconsin-Madison, United States; (2) Microsoft Research Asia, China; (3) Institute of Software, Chinese Academy of Sciences, China |
| 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. |
| Keyword | Algorithms Polynomial Approximation Theorem Proving |
| Sponsorship | ACM Spec. Interest Group. Algorithms Comput. Theory (SIGACT); SIAM Activity Group on Discrete Mathematics |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/14323 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Cai Jin-Yi,Lu Pinyan,Xia Mingji. dichotomy for holant* problems of boolean domain[C]. United States,2011:1714-1728. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| dichotomy for holant（366KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment