A computational proof of complexity of some restricted counting problems

DOI10.1016/J.TCS.2010.10.039MaRDI QIDQ534558zbMATHOpenAlexFDO

Authors 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)

Recommendations

• A Computational Proof of Complexity of Some Restricted Counting Problems
• Computational complexity of counting problems on 3-regular planar graphs
• Computational complexity of Holant problems
• Holant problems and counting CSP
• Holant problems for 3-regular graphs with complex edge functions

Cites work

• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 1157663 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• A Computational Proof of Complexity of Some Restricted Counting Problems
• A complexity dichotomy for partition functions with mixed signs
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
• Holant problems and counting CSP
• Holographic algorithms: from art to science
• On counting homomorphisms to directed acyclic graphs
• On the complexity of H-coloring
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of counting in sparse, regular, and planar graphs
• The complexity of partition functions
• Towards a dichotomy theorem for the counting constraint satisfaction problem

Cited in

(12)

• A complete dichotomy rises from the capture of vanishing signatures
• scientific article; zbMATH DE number 15994 (Why is no real title available?)
• A Computational Proof of Complexity of Some Restricted Counting Problems
• Computational complexity of counting problems on 3-regular planar graphs
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• Holographic reduction, interpolation and hardness
• Spin systems on \(k\)-regular graphs with complex edge functions
• Holant problems for 3-regular graphs with complex edge functions
• A dichotomy for real weighted Holant problems
• On the Complexity of Holant Problems
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)

This page was built for publication: A computational proof of complexity of some restricted counting problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534558)