ISCAS OpenIR  > 基础软件与系统重点实验室
a computational proof of complexity of some restricted counting problems
Cai Jin-Yi; Lu Pinyan; Xia Mingji
2009
会议名称6th Annual Conference on Theory and Applications of Models of Computation, TAMC 2009
会议录名称Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码138-149
会议日期43969
会议地点Changsha, China
收录类别其他
出版地Germany
出版者Germany
ISSN3029743
ISBN9783642020162
部门归属(1) Computer Sciences Department, University of Wisconsin, Madison, WI 53706, United States; (2) Microsoft Research Asia, Beijing, 100190, China; (3) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China
摘要We explore a computational approach to proving intractability of certain counting problems. More specifically we study the complexity of Holant of 3-regular graphs. These problems 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 r2 induced by some combinatorial constructions. These maps define sufficiently complicated dynamics of r2 that we can only analyze them computationally. 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. © Springer-Verlag Berlin Heidelberg 2009.
关键词Algebra
主办者South Central University
语种英语
内容类型会议论文
URI标识http://ir.iscas.ac.cn/handle/311060/8514
专题基础软件与系统重点实验室
推荐引用方式
GB/T 7714
Cai Jin-Yi,Lu Pinyan,Xia Mingji. a computational proof of complexity of some restricted counting problems[C]. Germany:Germany,2009:138-149.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
a computational proo(2593KB) 开放获取--请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Cai Jin-Yi]的文章
[Lu Pinyan]的文章
[Xia Mingji]的文章
百度学术
百度学术中相似的文章
[Cai Jin-Yi]的文章
[Lu Pinyan]的文章
[Xia Mingji]的文章
必应学术
必应学术中相似的文章
[Cai Jin-Yi]的文章
[Lu Pinyan]的文章
[Xia Mingji]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。