A computational proof of complexity of some restricted counting problems

DOI10.1016/j.tcs.2010.10.039zbMath1216.68122OpenAlexW2099255094MaRDI QIDQ534558

Jin-Yi Cai, Pinyan Lu, Mingji Xia

Publication date: 18 May 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.039

zbMATH Keywords

Holant problemholographic reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Signed and weighted graphs (05C22) Software, source code, etc. for problems pertaining to computer science (68-04)

Related Items

Holant problems for 3-regular graphs with complex edge functions ⋮ Holographic reduction, interpolation and hardness ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ On the Complexity of Holant Problems ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ A dichotomy for real weighted Holant problems

Cites Work

• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On the complexity of H-coloring
• Complexity of generalized satisfiability counting problems
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• On counting homomorphisms to directed acyclic graphs
• A Computational Proof of Complexity of Some Restricted Counting Problems
• Holant problems and counting CSP
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item