文章基本信息

标题：The Complexity of Weighted Boolean #CSP Modulo k
本地全文：下载
作者：Heng Guo ; Sangxia Huang ; Pinyan Lu 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：249-260
DOI：10.4230/LIPIcs.STACS.2011.249
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：#CSP; dichotomy theorem; counting problems; computational complexity