A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs
From MaRDI portal
Publication:3066165
DOI10.1007/978-3-642-17458-2_24zbMATH Open1310.68121arXiv1008.2688OpenAlexW3013402004MaRDI QIDQ3066165
Publication date: 8 January 2011
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Abstract: 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'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'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.
Full work available at URL: https://arxiv.org/abs/1008.2688
Related Items (2)
The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width
This page was built for publication: A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs
