The Complexity of Weighted Boolean #CSP

DOI10.1137/070690201MaRDI QIDQ3642870zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

Publication date 6 November 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0704.3683, http://eprints.whiterose.ac.uk/7981/1/Martin_Dyer_1.pdf

zbMATH Keywords

\#Pcomplexity theoryconstraint satisfactioncounting

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Abstract: This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterised by a finite set F of non-negative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that the partition function, i.e. the sum of the weights of all configurations, can be computed in polynomial time if either (1) every function in F is of ``product type, or (2) every function in F is ``pure affine. For every other fixed set F, computing the partition function is FP^{#P}-complete.

Recommendations

• The complexity of weighted Boolean \#CSP with mixed signs
• Complexity of counting CSP with complex weights
• The complexity of complex weighted Boolean \#CSP
• Complexity of counting CSP with complex weights
• The complexity of weighted Boolean \#CSP modulo \(k\)

Cited in

(51)

• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Classical simulation of quantum circuits by half Gauss sums
• Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
• 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
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• Definability for model counting
• A dichotomy for real weighted Holant problems
• Tractability in constraint satisfaction problems: a survey
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• A complete dichotomy rises from the capture of vanishing signatures
• The complexity of counting homomorphisms to cactus graphs modulo 2
• The complexity of weighted Boolean \#CSP modulo \(k\)
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• On the hardness of losing weight
• On the Hardness of Losing Weight
• The complexity of complex weighted Boolean \#CSP
• The complexity of weighted counting for acyclic conjunctive queries
• The complexity of weighted and unweighted \(\#\)CSP
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• The complexity of Boolean Holant problems with nonnegative weights
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Counting constraint satisfaction problems
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• Sum-of-Products with Default Values: Algorithms and Complexity Results
• A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
• scientific article; zbMATH DE number 7204481 (Why is no real title available?)
• Classification of a Class of Counting Problems Using Holographic Reductions
• Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
• Approximate counting via correlation decay in spin systems
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• Exponential time complexity of the complex weighted Boolean \#CSP
• A complexity trichotomy for k-regular asymmetric spin systems with complex edge functions
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs
• Weighted tiling systems for graphs: evaluation complexity
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Spin systems on k-regular graphs with complex edge functions
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
• Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
• On the complexity of \#CSP\(^d\)
• The complexity of approximating conservative counting CSPs
• The complexity of weighted Boolean \#CSP with mixed signs
• Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
• An approximation trichotomy for Boolean \#CSP

This page was built for publication: The Complexity of Weighted Boolean #CSP

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