The Complexity of the Counting Constraint Satisfaction Problem

DOI10.1007/978-3-540-70575-8_53MaRDI QIDQ3521956zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.642.8196

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of the counting constraint satisfaction problem
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Complexity of the counting constraint satisfaction problem
• Complexity of counting CSP with complex weights
• Complexity of counting CSP with complex weights

Cited in

(33)

• Holographic reduction, interpolation and hardness
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• Classical simulation of quantum circuits by half Gauss sums
• Dismantlability, connectedness, and mixing in relational structures
• A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
• Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
• Counting solutions to CSP using generating polynomials
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Counting List Matrix Partitions of Graphs
• Progress in complexity of counting problems
• Counting homomorphisms via hypergraph-based structural restrictions
• Complexity of the counting constraint satisfaction problem
• The complexity of complex weighted Boolean \#CSP
• The complexity of weighted counting for acyclic conjunctive queries
• Enumerating homomorphisms
• The complexity of weighted and unweighted \(\#\)CSP
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Generalized counting constraint satisfaction problems with determinantal circuits
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• Counting constraint satisfaction problems
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• The complexity of the counting constraint satisfaction problem
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Approximate counting via correlation decay in spin systems
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• Spin systems on k-regular graphs with complex edge functions
• Bounded degree nonnegative counting CSP
• The complexity of counting homomorphisms seen from the other side
• The complexity of approximating conservative counting CSPs
• 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

This page was built for publication: The Complexity of the Counting Constraint Satisfaction Problem

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