The complexity of weighted Boolean \#CSP with mixed signs

DOI10.1016/j.tcs.2009.06.003zbMath1171.68013OpenAlexW2112167630WikidataQ56323834 ScholiaQ56323834MaRDI QIDQ837186

Andrei A. Bulatov, Markus Jalsenius, David Richerby, Leslie Ann Goldberg, Martin Dyer

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.06.003

zbMATH Keywords

partition functionconstraint satisfactioncomplexity of counting

Mathematics Subject Classification ID

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

Related Items

Tractability in constraint satisfaction problems: a survey, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, The Complexity of Boolean Holant Problems with Nonnegative Weights, The complexity of complex weighted Boolean \#CSP, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, The complexity of weighted and unweighted \(\#\)CSP, Holographic algorithms beyond matchgates, Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS, Counting Constraint Satisfaction Problems., The complexity of planar Boolean \#CSP with complex weights, The complexity of approximating conservative counting CSPs, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, A dichotomy for real weighted Holant problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of complex weighted Boolean \#CSP
• Inapproximability of the Tutte polynomial
• An approximation trichotomy for Boolean \#CSP
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Complexity of generalized satisfiability counting problems
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of the Counting Constraint Satisfaction Problem
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of satisfiability problems