Complexity of counting CSP with complex weights

DOI10.1145/2822891MaRDI QIDQ4640291zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Xi Chen

Publication date 17 May 2018

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

Full work available at URL https://arxiv.org/abs/1111.2384

zbMATH Keywords

complexity dichotomyconstraint satisfaction problemcounting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30)

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}.

Recommendations

• Complexity of counting CSP with complex weights
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• The complexity of complex weighted Boolean \#CSP
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• The complexity of weighted and unweighted \(\#\)CSP

Cited in

(47)

• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• The complexity of weighted and unweighted \(\#\)CSP
• Planar \#CSP equality corresponds to quantum isomorphism -- a Holant viewpoint
• Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
• The complexity of the counting constraint satisfaction problem
• The complexity of weighted Boolean \#CSP with mixed signs
• Complexity of counting CSP with complex weights
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• scientific article; zbMATH DE number 7651202 (Why is no real title available?)
• Counting problems in parameterized complexity
• Exponential time complexity of the complex weighted Boolean \#CSP
• Approximate counting for spin systems in sub-quadratic time
• The complexity of Boolean Holant problems with nonnegative weights
• Optimal polynomial-time compression for Boolean Max CSP
• Zero-freeness and approximation of real Boolean Holant problems
• Restricted Holant dichotomy on domains 3 and 4
• The complexity of weighted Boolean \#CSP modulo \(k\)
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• Perfect matchings, rank of connection tensors and graph homomorphisms
• The complexity of complex weighted Boolean \#CSP
• Approximability of the eight-vertex model
• On the complexity of \#CSP\(^d\)
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• Symmetries and complexity (invited talk)
• On counting (quantum-)graph homomorphisms in finite fields of prime order
• From holant to quantum entanglement and back
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• 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
• Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
• Dichotomy result on 3-regular bipartite non-negative functions
• Bipartite 3-regular counting problems with mixed signs
• Complexity classification of the eight-vertex model
• Approximate counting for spin systems in sub-quadratic time
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• 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\)
• A characterization of efficiently compilable constraint languages
• The Complexity of the Counting Constraint Satisfaction Problem
• A combinatorial view of Holant problems on higher domains
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs
• A structured view on weighted counting with relations to counting, quantum computation and applications
• Approximability of the complementarily symmetric Holant problems on cubic graphs

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)