A computational proof of complexity of some restricted counting problems
From MaRDI portal
Publication:534558
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
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