the complexity of weighted boolean #csp modulo k
文献类型：会议论文
| 作者 | Guo Heng ; Huang Sangxia ; Lu Pinyan ; Xia Mingji |
| 出版日期 | 2011 |
| 会议名称 | 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 |
| 会议日期 | March 10, 2011 - March 12, 2011 |
| 会议地点 | Dortmund, Germany |
| 关键词 | Computational complexity |
| 页码 | 249-260 |
| 中文摘要 | 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. |
| 收录类别 | EI |
| 会议录 | Leibniz International Proceedings in Informatics, LIPIcs
 |
| 语种 | 英语 |
| ISSN号 | 1868-8969 |
| ISBN号 | 9783939897255 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16368]  |
| 专题 | 软件研究所_软件所图书馆_会议论文 |
| 推荐引用方式 GB/T 7714 | Guo Heng,Huang Sangxia,Lu Pinyan,et al. the complexity of weighted boolean #csp modulo k[C]. 见:28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. Dortmund, Germany. March 10, 2011 - March 12, 2011. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。