Approximate counting for complex-weighted Boolean constraint satisfaction problems
From MaRDI portal
Publication:690490
DOI10.1016/j.ic.2012.08.002zbMath1323.68324arXiv1007.0391OpenAlexW2569211458MaRDI QIDQ690490
Publication date: 27 November 2012
Published in: Information and Computation, Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1007.0391
signatureconstraintconstraint satisfaction problemdichotomy theoremHolant problemapproximation-preserving reductionT-constructibility
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)
Related Items
A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Approximate counting for complex-weighted Boolean constraint satisfaction problems ⋮ Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems ⋮ The complexity of approximating conservative counting CSPs
Cites Work
- The complexity of computing the permanent
- Holographic algorithms: from art to science
- Approximate counting for complex-weighted Boolean constraint satisfaction problems
- An approximation trichotomy for Boolean \#CSP
- \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
- Expressiveness of matchgates.
- The relative complexity of approximate counting problems
- Complexity of generalized satisfiability counting problems
- The Complexity of Approximating Bounded-Degree Boolean #CSP
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- 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
- ANALYSIS OF QUANTUM FUNCTIONS
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item