holographic reduction, interpolation and hardness
文献类型：期刊论文
| 作者 | Cai Jin-Yi ; Lu Pinyan ; Xia Mingji |
| 刊名 | COMPUTATIONAL COMPLEXITY
 |
| 出版日期 | 2012 |
| 卷号 | 21期号:4页码:573-604 |
| 关键词 | Holographic reduction polynomial interpolation #P-hard counting complexity |
| ISSN号 | 1016-3328 |
| 中文摘要 | 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. |
| 学科主题 | Computer Science ; Mathematics |
| 收录类别 | SCI |
| 资助信息 | NSF CCF-0914969; NSFC 61003030; Institute of Software, Chinese Academy of Sciences |
| 语种 | 英语 |
| WOS记录号 | WOS:000310245900002 |
| 公开日期 | 2013-09-17 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/15049]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。