The complexity of complex weighted Boolean #CSP

作者：

Highlights：

• Define and analyze two families of constraint functions: the product type and the affine type.

• Prove that for Boolean #CSP problems these families define polynomial time computable problems, and everything else is #P-hard.

• Extend this complexity dichotomy to Read-At-Most-Thrice Boolean #CSP.

• Introduce local holographic transformations.

摘要

•Define and analyze two families of constraint functions: the product type and the affine type.•Prove that for Boolean #CSP problems these families define polynomial time computable problems, and everything else is #P-hard.•Extend this complexity dichotomy to Read-At-Most-Thrice Boolean #CSP.•Introduce local holographic transformations.

论文关键词：CSP,Counting problems,Dichotomy theorem

论文评审过程：Received 16 July 2012, Revised 5 June 2013, Accepted 11 July 2013, Available online 24 July 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.07.003