Approximate counting for complex-weighted Boolean constraint satisfaction problems

DOI10.1007/978-3-642-18318-8_23zbMATH Open1323.68324arXiv1007.0391OpenAlexW2569211458MaRDI QIDQ690490FDOQ690490

Tomoyuki Yamakami

Publication date: 27 November 2012

Published in: Information and Computation, Approximation and Online Algorithms (Search for Journal in Brave)

Abstract: Constraint satisfaction problems (or CSPs) have been extensively studied in, for instance, artificial intelligence, database theory, graph theory, and statistical physics. From a practical viewpoint, it is beneficial to approximately solve those CSPs. When one tries to approximate the total number of truth assignments that satisfy all Boolean-valued constraints for (unweighted) Boolean CSPs, there is a known trichotomy theorem by which all such counting problems are neatly classified into exactly three categories under polynomial-time (randomized) approximation-preserving reductions. In contrast, we obtain a dichotomy theorem of approximate counting for complex-weighted Boolean CSPs, provided that all complex-valued unary constraints are freely available to use. It is the expressive power of free unary constraints that enables us to prove such a stronger, complete classification theorem. This discovery makes a step forward in the quest for the approximation-complexity classification of all counting CSPs. To deal with complex weights, we employ proof techniques of factorization and arity reduction along the line of solving Holant problems. Moreover, we introduce a novel notion of T-constructibility that naturally induces approximation-preserving reducibility. Our result also gives an approximation analogue of the dichotomy theorem on the complexity of exact counting for complex-weighted Boolean CSPs.

Full work available at URL: https://arxiv.org/abs/1007.0391

Recommendations

• Approximate counting for complex-weighted Boolean constraint satisfaction problems
• A trichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• An approximation trichotomy for Boolean \#CSP
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems (extended abstract)

zbMATH Keywords

constraintsignatureconstraint satisfaction problemdichotomy theoremHolant problemapproximation-preserving reductionT-constructibility

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cites Work

• The complexity of computing the permanent
• The relative complexity of approximate counting problems
• 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
• Title not available (Why is that?)
• An approximation trichotomy for Boolean \#CSP
• Complexity of generalized satisfiability counting problems
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic algorithms: from art to science
• Mathematical Foundations of Computer Science 2003
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
• The Complexity of Approximating Bounded-Degree Boolean #CSP
• Signature Theory in Holographic Algorithms
• ANALYSIS OF QUANTUM FUNCTIONS
• Expressiveness of matchgates.
• Log-supermodular functions, functional clones and counting CSPs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximate counting for complex-weighted Boolean constraint satisfaction problems

Cited In (4)

• Approximate counting for complex-weighted Boolean constraint satisfaction problems
• The complexity of approximating conservative counting CSPs
• Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
• A structured view on weighted counting with relations to counting, quantum computation and applications

This page was built for publication: Approximate counting for complex-weighted Boolean constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690490)