Approximate counting for complex-weighted Boolean constraint satisfaction problems

DOI10.1016/j.ic.2012.08.002zbMath1323.68324arXiv1007.0391OpenAlexW2569211458MaRDI QIDQ690490

Tomoyuki Yamakami

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

zbMATH Keywords

signatureconstraintconstraint satisfaction problemdichotomy theoremHolant problemapproximation-preserving reductionT-constructibility

Mathematics Subject Classification ID

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