Institutional Repository
| the complexity of weighted boolean #csp modulo k | |
| Guo Heng; Huang Sangxia; Lu Pinyan; Xia Mingji | |
| 2011 | |
| Conference Name | 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 |
| Source | Leibniz International Proceedings in Informatics, LIPIcs |
| Pages | 249-260 |
| Conference Date | March 10, 2011 - March 12, 2011 |
| Conference Place | Dortmund, Germany |
| Indexed Type | EI |
| ISSN | 1868-8969 |
| ISBN | 9783939897255 |
| Department | (1) University of Wisconsin-Madison Madison WI 53706 United States; (2) KTH - Royal Institute of Technology Stockholm Sweden; (3) Microsoft Research Asia Beijing China; (4) Institute of Software Chinese Academy of Sciences Beijing 100190 China |
| English Abstract | We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer k > 1. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k. © Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia.; We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer k > 1. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k. © Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia. |
| Keyword | Computational Complexity |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16368 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Guo Heng,Huang Sangxia,Lu Pinyan,et al. the complexity of weighted boolean #csp modulo k[C],2011:249-260. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment