Nonnegative weighted \#CSP: an effective complexity dichotomy
From MaRDI portal
Nonnegative weighted \CSP: an effective complexity dichotomy
Abstract: We prove a complexity dichotomy theorem for all non-negative weighted counting Constraint Satisfaction Problems (CSP). This caps a long series of important results on counting problems including unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the counting CSP problem defined by F is solvable in polynomial time; if it does not satisfy the criterion, then the problem is #P-hard. We furthermore show that the question of whether F satisfies the criterion is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of problems, although when specialized to those cases, they are logically equivalent. Our proof mainly uses Linear Algebra, and represents a departure from Universal Algebra, the dominant methodology in recent years.
Recommendations
Cites work
- A complete dichotomy rises from the capture of vanishing signatures
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A new line of attack on the dichotomy conjecture
- A Simple Algorithm for Mal'tsev Constraints
- Algorithms in Algebraic Number Theory
- An algebraic approach to multi-sorted constraints
- An effective dichotomy for the counting constraint satisfaction problem
- Approximation resistant predicates from pairwise independence
- Complexity of counting CSP with complex weights
- Conditional Hardness for Approximate Coloring
- Constraints, consistency and closure
- CSP gaps and reductions in the lasserre hierarchy
- Dichotomy for Holant* problems of Boolean domain
- Dichotomy for Holant* problems with a function on domain size 3
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Graph homomorphisms with complex values: a dichotomy theorem
- Holant problems and counting CSP
- Holographic Algorithms
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- How to Round Any CSP
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 4035895 (Why is no real title available?)
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- On counting homomorphisms to directed acyclic graphs
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- Operations with structures
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Recent Results on the Algebraic Approach to the CSP
- Some optimal inapproximability results
- The complexity of partition functions
- The complexity of satisfiability problems
- The complexity of the counting constraint satisfaction problem
- The complexity of weighted and unweighted \(\#\)CSP
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The structure of finite algebras
- Towards a dichotomy theorem for the counting constraint satisfaction problem
Cited in
(30)- The complexity of counting \(\mathrm{CSP}^d\)
- What can be sampled locally?
- 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
- A dichotomy for real weighted Holant problems
- An effective dichotomy for the counting constraint satisfaction problem
- The complexity of weighted and unweighted \(\#\)CSP
- The complexity of Boolean Holant problems with nonnegative weights
- Complexity of counting CSP with complex weights
- Complexity of counting CSP with complex weights
- Approximate counting via correlation decay in spin systems
- Dichotomy result on 3-regular bipartite non-negative functions
- Bipartite 3-regular counting problems with mixed signs
- Dichotomy result on 3-regular bipartite non-negative functions
- Bipartite 3-regular counting problems with mixed signs
- Complexity classification of the eight-vertex model
- The computational complexity of Holant problems on 3-regular graphs
- The complexity of counting planar graph homomorphisms of domain size 3
- Bounded degree nonnegative counting CSP
- Exponential time complexity of the complex weighted Boolean \#CSP
- Restricted Holant dichotomy on domains 3 and 4
- Restricted Holant dichotomy on domain sizes 3 and 4
- From holant to quantum entanglement and back
- Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
- A combinatorial view of Holant problems on higher domains
- Planar \#CSP equality corresponds to quantum isomorphism -- a Holant viewpoint
- Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
- On the complexity of \#CSP\(^d\)
- P-time algorithms for typical \#EO problems
- The complexity of weighted Boolean \#CSP with mixed signs
This page was built for publication: Nonnegative weighted \#CSP: an effective complexity dichotomy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179267)
