The computational complexity of Holant problems on 3-regular graphs

DOI10.1016/J.TCS.2023.114256MaRDI QIDQ6199389zbMATH OpenFDO

Authors Peng Yang, Yuan Huang, Zhiguo Fu

Publication date 23 February 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2023.114256

zbMATH Keywords

computational complexitydichotomyHolant problemsSLOCC

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A complete dichotomy rises from the capture of vanishing signatures
• A dichotomy for real weighted Holant problems
• An effective dichotomy for the counting constraint satisfaction problem
• Complexity Dichotomies for Counting Problems
• Complexity of counting CSP with complex weights
• Dichotomy for Holant* problems of Boolean domain
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Graph homomorphisms with complex values: a dichotomy theorem
• Holant problems and counting CSP
• Holographic Algorithms
• Holographic algorithms by Fibonacci gates
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of Boolean Holant problems with nonnegative weights
• The complexity of complex weighted Boolean \#CSP
• The complexity of partition functions
• The complexity of symmetric Boolean parity Holant problems
• The complexity of the counting constraint satisfaction problem
• The complexity of weighted and unweighted \(\#\)CSP

This page was built for publication: The computational complexity of Holant problems on 3-regular graphs

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