Complexity of counting CSP with complex weights
From MaRDI portal
Publication:4640291
DOI10.1145/2822891zbMATH Open1426.68114arXiv1111.2384OpenAlexW2626596188MaRDI QIDQ4640291FDOQ4640291
Authors: Jin-Yi Cai, Xi Chen 
Publication date: 17 May 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Abstract: We give a complexity dichotomy theorem for the counting Constraint Satisfaction Problem (#CSP in short) with complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions, then we prove that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our complexity dichotomy generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when there is a single symmetric binary function in F; (b) the problem of counting directed graph homomorphisms is the special case when there is a single not-necessarily-symmetric binary function in F; and (c) the standard form of #CSP is when all functions in F take values in {0,1}.
Full work available at URL: https://arxiv.org/abs/1111.2384
Recommendations
Cited In (35)
- The complexity of weighted and unweighted \(\#\)CSP
- Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
- The complexity of the counting constraint satisfaction problem
- Complexity of counting CSP with complex weights
- Title not available (Why is that?)
- The complexity of weighted Boolean \#CSP with mixed signs
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Counting problems in parameterized complexity
- Exponential time complexity of the complex weighted Boolean \#CSP
- The complexity of Boolean Holant problems with nonnegative weights
- Restricted Holant dichotomy on domains 3 and 4
- The complexity of weighted Boolean \#CSP modulo \(k\)
- Zero-freeness and approximation of real Boolean Holant problems
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Perfect matchings, rank of connection tensors and graph homomorphisms
- Approximability of the eight-vertex model
- The complexity of complex weighted Boolean \#CSP
- A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
- The computational complexity of Holant problems on 3-regular graphs
- A complexity trichotomy for \(k\)-regular asymmetric spin systems with complex edge functions
- 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
- Title not available (Why is that?)
- Restricted Holant dichotomy on domain sizes 3 and 4
- The complexity of counting planar graph homomorphisms of domain size 3
- The Complexity of Weighted Boolean #CSP
- The complexity of counting \(\mathrm{CSP}^d\)
- The Complexity of the Counting Constraint Satisfaction Problem
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- Approximability of the complementarily symmetric Holant problems on cubic graphs
- A structured view on weighted counting with relations to counting, quantum computation and applications
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
This page was built for publication: Complexity of counting CSP with complex weights
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640291)
