The complexity of the counting constraint satisfaction problem

DOI10.1145/2528400zbMath1281.68130OpenAlexW2078752178MaRDI QIDQ5395730

Andrei A. Bulatov

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2528400

zbMATH Keywords

complexityconstraint satisfaction problemcounting problemsdichotomy theoremhomomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Operations and polynomials in algebraic structures, primal algebras (08A40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (37)

Tractability in constraint satisfaction problems: a survey ⋮ Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ Zero-freeness and approximation of real Boolean Holant problems ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Counting \(4 \times 4\) matrix partitions of graphs ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Uniform Reliability of Self-Join-Free Conjunctive Queries ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximability of the complementarily symmetric Holant problems on cubic graphs ⋮ A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory ⋮ Complexity classification of the eight-vertex model ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ CSP beyond tractable constraint languages ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS ⋮ A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory ⋮ Counting Constraint Satisfaction Problems. ⋮ Organization mechanism and counting algorithm on vertex-cover solutions ⋮ Boolean max-co-clones ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ Unnamed Item ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Unnamed Item ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ Approximability of the eight-vertex model ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ The complexity of counting \(\mathrm{CSP}^d\) ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ Lifted Reasoning for Combinatorial Counting ⋮ A dichotomy for real weighted Holant problems

This page was built for publication: The complexity of the counting constraint satisfaction problem