holographic reduction, interpolation and hardness

ISCAS OpenIR

	holographic reduction, interpolation and hardness
	Cai Jin-Yi; Lu Pinyan; Xia Mingji
	2012
发表期刊	COMPUTATIONAL COMPLEXITY
ISSN	1016-3328
卷号	21 期号:4 页码:573-604
摘要	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.
收录类别	SCI
关键词	Holographic Reduction Polynomial Interpolation #p-hard Counting Complexity
部门归属	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.
学科领域	Computer Science ; Mathematics
资助者	NSF CCF-0914969; NSFC 61003030; Institute of Software, Chinese Academy of Sciences
语种	英语
WOS记录号	WOS:000310245900002
引用统计	被引频次：14[WOS] [WOS记录] [WOS相关记录]
内容类型	期刊论文
URI标识	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.