The complexity of complex weighted Boolean \#CSP

DOI10.1016/j.jcss.2013.07.003zbMath1311.68074MaRDI QIDQ395011

Jin-Yi Cai, Pinyan Lu, Mingji Xia

Publication date: 28 January 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2013.07.003

zbMATH Keywords

CSP; counting problems; dichotomy theorem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

The Complexity of Boolean Holant Problems with Nonnegative Weights, Unnamed Item, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory, On the Complexity of Holant Problems, Counting Constraint Satisfaction Problems., Approximability of the eight-vertex model, A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory, Complexity classification of the eight-vertex model, The computational complexity of Holant problems on 3-regular graphs, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs, The complexity of weighted Boolean \#CSP with mixed signs, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Computing and estimating the volume of the solution space of SMT(LA) constraints, The complexity of approximating complex-valued Ising and Tutte partition functions, Holographic algorithms beyond matchgates, Complexity classification of the six-vertex model, Clifford gates in the Holant framework, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, FKT is not universal -- a planar holant dichotomy for symmetric constraints, The complexity of counting \(\mathrm{CSP}^d\), Classical simulation of quantum circuits by half Gauss sums, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, 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, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin

Cites Work

• Unnamed Item
• Unnamed Item
• Holographic algorithms: from art to science
• The complexity of weighted Boolean \#CSP with mixed signs
• Complexity of generalized satisfiability counting problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• On the complexity of #CSP
• From Holant to #CSP and Back: Dichotomy for Holant c Problems
• Computational Complexity of Holant Problems
• The Complexity of the Counting Constraint Satisfaction Problem
• Holographic Algorithms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On counting homomorphisms to directed acyclic graphs
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• Holant problems and counting CSP
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of satisfiability problems
• Complexity of counting CSP with complex weights
• Automata, Languages and Programming
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem