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 |
| 会议日期 | 43969 |
| 会议地点 | Changsha, China |
| 关键词 | Algebra |
| 页码 | 138-149 |
| 英文摘要 | 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. |
| 收录类别 | 其他 |
| 会议主办者 | South Central University |
| 会议录 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 |
| 会议录出版者 | Germany |
| 会议录出版地 | Germany |
| 语种 | 英语 |
| ISSN号 | 3029743 |
| ISBN号 | 9783642020162 |
| 源URL | [http://124.16.136.157/handle/311060/8514]  |
| 专题 | 软件研究所_计算机科学国家重点实验室 _会议论文 |
| 推荐引用方式 GB/T 7714 | Cai Jin-Yi,Lu Pinyan,Xia Mingji. a computational proof of complexity of some restricted counting problems[C]. 见:6th Annual Conference on Theory and Applications of Models of Computation, TAMC 2009. Changsha, China. 43969. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。