the complexity of weighted boolean #csp modulo k

ISCAS OpenIR

	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
会议录名称	Leibniz International Proceedings in Informatics, LIPIcs
页码	249-260
会议日期	March 10, 2011 - March 12, 2011
会议地点	Dortmund, Germany
收录类别	EI
ISSN	1868-8969
ISBN	9783939897255
部门归属	(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
摘要	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.
关键词	Computational Complexity
语种	英语
内容类型	会议论文
URI标识	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],2011:249-260.