holographic reduction, interpolation and hardness

CORC > 软件研究所 > 软件所图书馆 > 期刊论文

	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.