a computational proof of complexity of some restricted counting problems

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

	a computational proof of complexity of some restricted counting problems
	Jin-Yi Cai ; Pinyan Lu ; Mingji Xia
刊名	Theoretical Computer Science
	2010
页码	-
关键词	Holant problem Holographic reduction
ISSN号	0304-3975
收录类别	SCIENCEDIRECT,EI
语种	英语
公开日期	2011-05-23
附注	We explore a computational approach to proving the intractability of certain counting problems. These problems can be described in various ways, and they include concrete problems such as counting the number of vertex covers or independent sets for 3-regular graphs. The high level principle of our approach is algebraic, which provides sufficient conditions for interpolation to succeed. Another algebraic component is holographic reductions. We then analyze in detail polynomial maps on induced by some combinatorial constructions. These maps define sufficiently complicated dynamics of that we can only analyze them computationally. In this paper we use both numerical computation (as intuitive guidance) and symbolic computation (as proof theoretic verification) to derive that a certain collection of combinatorial constructions, in myriad combinations, fulfills the algebraic requirements of proving #P-hardness. The final result is a dichotomy theorem for a class of counting problems. This includes a class of generic holant problems with an arbitrary real valued edge signature over (2,3)-regular undirected graphs. In particular, it includes all partition functions with 0-1 vertex assignments and an arbitrary real valued edge function over all 3-regular undirected graphs.
内容类型	期刊论文
源URL	[http://124.16.136.157/handle/311060/9648]
专题	软件研究所_软件所图书馆_期刊论文
推荐引用方式 GB/T 7714	Jin-Yi Cai,Pinyan Lu,Mingji Xia. a computational proof of complexity of some restricted counting problems[J]. Theoretical Computer Science,2010:-.
APA	Jin-Yi Cai,Pinyan Lu,&Mingji Xia.(2010).a computational proof of complexity of some restricted counting problems.Theoretical Computer Science,-.
MLA	Jin-Yi Cai,et al."a computational proof of complexity of some restricted counting problems".Theoretical Computer Science (2010):-.