The complexity of weighted and unweighted \#CSP

DOI10.1016/J.JCSS.2011.12.002zbMATH Open1282.68110DBLPjournals/jcss/BulatovDGJJR12OpenAlexW2134600856WikidataQ56323825 ScholiaQ56323825MaRDI QIDQ414939FDOQ414939

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

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

zbMATH Keywords

complexity theoryconstraint satisfactioncounting

Mathematics Subject Classification ID

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

Cites Work

• The relative complexity of approximate counting problems
• On the complexity of \#CSP
• Title not available (Why is that?)
• 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
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• The Complexity of the Counting Constraint Satisfaction Problem
• An approximation trichotomy for Boolean \#CSP
• Complexity of generalized satisfiability counting problems
• Title not available (Why is that?)
• Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
• The complexity of approximating bounded-degree Boolean \#CSP
• A complexity dichotomy for partition functions with mixed signs
• A complexity dichotomy for hypergraph partition functions

Cited In (17)

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