A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs

作者：Yamakami Tomoyuki^*

来源：Theoretical Computer Science, 2012, 447: 120-135.

DOI：10.1016/j.tcs.2012.03.036

• Constraint satisfaction problem #CSP
• Bounded degree
• Approximate counting
• Dichotomy theorem
• T-constructibility
• Signature
• Holant problem

We determine the computational complexity of approximately counting the total weight of variable assignments for every complex-weighted Boolean constraint satisfaction problem (or CSP) with any number of additional unary (i.e., arity 1) constraints, particularly, when degrees of input instances are bounded from above by a fixed constant. All degree-1 counting CSPs are obviously solvable in polynomial time. When the instance%26apos;s degree is more than two, we present a dichotomy theorem that classifies all counting CSPs admitting free unary constraints into exactly two categories. This classification theorem extends, to complex-weighted problems, an earlier result on the approximation complexity of unweighted counting Boolean CSPs of bounded degree. The framework of the proof of our theorem is based on a theory of signature developed from Valiant%26apos;s holographic algorithms that can efficiently solve seemingly intractable counting CSPs. Despite the use of arbitrary complex weight, our proof of the classification theorem is rather elementary and intuitive due to an extensive use of a novel notion of limited T-constructibility. For the remaining degree-2 problems, in contrast, they are as hard to approximate as Holant problems, which are a generalization of counting CSPs.

• 出版日期2012-8-17