The complexity of weighted and unweighted \#CSP

DOI10.1016/J.JCSS.2011.12.002MaRDI QIDQ414939zbMATHOpenAlexDBLPWikidataFDO

Authors Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby, Mark 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

complexity theoryconstraint satisfactioncounting

Mathematics Subject Classification ID

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

Recommendations

• Complexity of counting CSP with complex weights
• Complexity of counting CSP with complex weights
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• The Complexity of Weighted Boolean #CSP
• The complexity of weighted Boolean \#CSP with mixed signs

Cites work

• scientific article; zbMATH DE number 5999552 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• A complexity dichotomy for hypergraph partition functions
• A complexity dichotomy for partition functions with mixed signs
• An approximation trichotomy for Boolean \#CSP
• Complexity of generalized satisfiability counting problems
• Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
• Holant problems and counting CSP
• On counting homomorphisms to directed acyclic graphs
• On the complexity of \#CSP
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Weighted Boolean #CSP
• The Complexity of the Counting Constraint Satisfaction Problem
• The complexity of approximating bounded-degree Boolean \#CSP
• The complexity of weighted Boolean \#CSP with mixed signs
• The relative complexity of approximate counting problems
• Towards a dichotomy theorem for the counting constraint satisfaction problem

Cited in

(17)

• The complexity of weighted counting for acyclic conjunctive queries
• The complexity of weighted Boolean \#CSP with mixed signs
• Complexity of counting CSP with complex weights
• The complexity of counting planar graph homomorphisms of domain size 3
• A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
• Complexity of counting CSP with complex weights
• The effect of combination functions on the complexity of relational Bayesian networks
• Complexity classification of the eight-vertex model
• A structured view on weighted counting with relations to counting, quantum computation and applications
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• The complexity of approximating conservative counting CSPs
• The computational complexity of Holant problems on 3-regular graphs
• The complexity of Bayesian networks specified by propositional and relational languages
• The complexity of Boolean Holant problems with nonnegative weights
• Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
• The weight in enumeration

This page was built for publication: The complexity of weighted and unweighted \(\#\)CSP

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