Holographic reduction for some counting problems

DOI10.1016/j.ipl.2011.05.012zbMath1260.68165OpenAlexW2060232838MaRDI QIDQ1944130

Chen Yuan, Haibin Kan

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.05.012

zbMATH Keywords

computational complexitydichotomy\#Pholographic reduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Holographic algorithms by Fibonacci gates
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• From Holant to #CSP and Back: Dichotomy for Holant c Problems
• Some Results on Matchgates and Holographic Algorithms
• The Complexity of Enumeration and Reliability Problems
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

This page was built for publication: Holographic reduction for some counting problems