Institutional Repository
| a computational proof of complexity of some restricted counting problems | |
| Cai Jin-Yi; Lu Pinyan; Xia Mingji | |
| 2009 | |
| Conference Name | 6th Annual Conference on Theory and Applications of Models of Computation, TAMC 2009 |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Pages | 138-149 |
| Conference Date | 43969 |
| Conference Place | Changsha, China |
| Indexed Type | 其他 |
| Publish Place | Germany |
| Publisher | Germany |
| ISSN | 3029743 |
| ISBN | 9783642020162 |
| Department | (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 |
| English Abstract | 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. |
| Keyword | Algebra |
| Sponsorship | South Central University |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8514 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation 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. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| a computational proo（2593KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment