The Complexity of Boolean Holant Problems with Nonnegative Weights

DOI10.1137/17M113304XzbMath1397.68105OpenAlexW2807924989MaRDI QIDQ4571918

Hanpin Wang, Jiabao Lin

Publication date: 4 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m113304x

zbMATH Keywords

dichotomycounting complexity\(\#\)CSPHolant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Zero-freeness and approximation of real Boolean Holant problems, Approximability of the complementarily symmetric Holant problems on cubic graphs, 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, Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS, Dichotomy result on 3-regular bipartite non-negative functions, Dichotomy result on 3-regular bipartite non-negative functions, FKT is not universal -- a planar holant dichotomy for symmetric constraints, The complexity of counting \(\mathrm{CSP}^d\)

Cites Work

• A dichotomy for real weighted Holant problems
• The complexity of complex weighted Boolean \#CSP
• The complexity of weighted and unweighted \(\#\)CSP
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Holographic algorithms beyond matchgates
• Complexity of generalized satisfiability counting problems
• Valiant's holant theorem and matchgate tensors
• The complexity of partition functions
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Computational Complexity of Holant Problems
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• The Complexity of Weighted Boolean #CSP
• On the Structure of Polynomial Time Reducibility
• Complexity of Counting CSP with Complex Weights
• Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
• A New Holant Dichotomy Inspired by Quantum Computation
• Holant problems and counting CSP
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• Operations with structures
• The Complexity of Symmetric Boolean Parity Holant Problems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item