The complexity of weighted and unweighted \(\#\)CSP

DOI10.1016/j.jcss.2011.12.002zbMath1282.68110OpenAlexW2134600856WikidataQ56323825 ScholiaQ56323825MaRDI QIDQ414939

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

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.12.002

zbMATH Keywords

countingconstraint satisfactioncomplexity theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, The Complexity of Boolean Holant Problems with Nonnegative Weights, The effect of combination functions on the complexity of relational Bayesian networks, The complexity of weighted counting for acyclic conjunctive queries, Complexity classification of the eight-vertex model, The computational complexity of Holant problems on 3-regular graphs, The complexity of Bayesian networks specified by propositional and relational languages, 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, The Weight in Enumeration, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, The complexity of approximating conservative counting CSPs, A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights

Cites Work

• A complexity dichotomy for hypergraph partition functions
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• An approximation trichotomy for Boolean \#CSP
• The relative complexity of approximate counting problems
• Complexity of generalized satisfiability counting problems
• On the complexity of #CSP
• The Complexity of Approximating Bounded-Degree Boolean #CSP
• The Complexity of the Counting Constraint Satisfaction Problem
• On counting homomorphisms to directed acyclic graphs
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• Holant problems and counting CSP
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item