The complexity of complex weighted Boolean \#CSP

DOI10.1016/j.jcss.2013.07.003zbMath1311.68074OpenAlexW1997590411MaRDI 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

CSPcounting problemsdichotomy theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (28)

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

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

This page was built for publication: The complexity of complex weighted Boolean \#CSP