Institutional Repository
| holographic reduction, interpolation and hardness | |
| Cai Jin-Yi; Lu Pinyan; Xia Mingji | |
| 2012 | |
| Source | COMPUTATIONAL COMPLEXITY
 |
| ISSN | 1016-3328 |
| Volume | 21Issue:4Pages:573-604 |
| English Abstract | We introduce the method of proving complexity dichotomy theorems by holographic reductions. Combined with interpolation, we present a unified strategy to prove #P-hardness. Specifically, we prove a complexity dichotomy theorem for a class of counting problems on 2-3 regular graphs expressible by Boolean signatures. For these problems, whenever a holographic reduction followed by interpolation fails to prove #P-hardness, we can show that the problem is solvable in polynomial time.; We introduce the method of proving complexity dichotomy theorems by holographic reductions. Combined with interpolation, we present a unified strategy to prove #P-hardness. Specifically, we prove a complexity dichotomy theorem for a class of counting problems on 2-3 regular graphs expressible by Boolean signatures. For these problems, whenever a holographic reduction followed by interpolation fails to prove #P-hardness, we can show that the problem is solvable in polynomial time. |
| Indexed Type | SCI |
| Keyword | Holographic Reduction Polynomial Interpolation #p-hard Counting Complexity |
| Department | Cai Jin-Yi Univ Wisconsin Madison WI 53706 USA. Lu Pinyan Microsoft Res Asia Shanghai Peoples R China. Xia Mingji Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China. |
| Subject | Computer Science ; Mathematics |
| Sponsorship | NSF CCF-0914969; NSFC 61003030; Institute of Software, Chinese Academy of Sciences |
| Language | 英语 |
| WOS ID | WOS:000310245900002 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/15049 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Cai Jin-Yi,Lu Pinyan,Xia Mingji. holographic reduction, interpolation and hardness[J]. COMPUTATIONAL COMPLEXITY,2012,21(4):573-604. |
| APA | Cai Jin-Yi,Lu Pinyan,&Xia Mingji.(2012).holographic reduction, interpolation and hardness.COMPUTATIONAL COMPLEXITY,21(4),573-604. |
| MLA | Cai Jin-Yi,et al."holographic reduction, interpolation and hardness".COMPUTATIONAL COMPLEXITY 21.4(2012):573-604. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment