A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
From MaRDI portal
Publication:443724
DOI10.1016/j.tcs.2012.03.036zbMath1253.68184OpenAlexW1550829276MaRDI QIDQ443724
Publication date: 13 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.036
signatureconstraint satisfaction problemapproximate countingbounded degreedichotomy theorem\(\#\)CSPholant problemT-constructibility
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
Cites Work
- Unnamed Item
- Unnamed Item
- Holographic algorithms: from art to science
- An approximation trichotomy for Boolean \#CSP
- \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
- Complexity of generalized satisfiability counting problems
- The Complexity of Approximating Bounded-Degree Boolean #CSP
- On Counting Independent Sets in Sparse Graphs
- Holographic Algorithms
- Signature Theory in Holographic Algorithms
- The Complexity of Weighted Boolean #CSP
- On the Structure of Polynomial Time Reducibility
- Holant problems and counting CSP
- The complexity of satisfiability problems
- Mathematical Foundations of Computer Science 2003
- Fanout limitations on constraint systems
This page was built for publication: A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs