A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs

摘要

We determine the complexity of approximate counting of the total weight of assignments for complex-weighted Boolean constraint satisfaction problems (or CSPs), particularly, when degrees of instances are bounded from above by a given constant, provided that all arity-1 (or unary) constraints are freely available. All degree-1 counting CSPs are solvable in polynomial time. When the degree is more than 2, we present a trichotomy theorem that classifies all bounded-degree counting CSPs into only three categories. This classification extends to complex-weighted problems an earlier result on the complexity of the approximate counting of bounded-degree unweighted Boolean CSPs. The framework of the proof of our trichotomy theorem is based on Cai's theory of signatures used for holographic algorithms. For the degree-2 problems, we show that they are as hard to approximate as complex Holant problems.