热门
computational complexity of holant problems
文献类型：期刊论文
| 作者 | Cai Jin-Yi ; Lu Pinyan ; Xia Mingji |
| 刊名 | SIAM Journal on Computing
 |
| 出版日期 | 2011 |
| 卷号 | 40期号:4页码:1101-1132 |
| 关键词 | Boolean functions Interpolation Real variables |
| ISSN号 | 0097-5397 |
| 中文摘要 | We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free (Holant * problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free (Holantc problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. © 2011 Society for Industrial and Applied Mathematics. |
| 英文摘要 | We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free (Holant * problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free (Holantc problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. © 2011 Society for Industrial and Applied Mathematics. |
| 学科主题 | Computer Science ; Mathematics |
| 收录类别 | EI ; SCI |
| 资助信息 | NSFCCF-0830488, CCF-0914969, CCF-0511679; Chinese Academy of Sciences; NSFC61003030, 60970003 |
| 语种 | 英语 |
| WOS记录号 | WOS:000294296100006 |
| 公开日期 | 2013-10-08 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16071]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Cai Jin-Yi,Lu Pinyan,Xia Mingji. computational complexity of holant problems[J]. SIAM Journal on Computing,2011,40(4):1101-1132. |
| APA | Cai Jin-Yi,Lu Pinyan,&Xia Mingji.(2011).computational complexity of holant problems.SIAM Journal on Computing,40(4),1101-1132. |
| MLA | Cai Jin-Yi,et al."computational complexity of holant problems".SIAM Journal on Computing 40.4(2011):1101-1132. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。