Exponential time complexity of the complex weighted Boolean \#CSP

DOI10.1007/978-3-031-49190-0_6MaRDI QIDQ6591459

Ying Liu

Publication date: 22 August 2024

zbMATH Keywords

computational complexitydichotomypinning\#CSPblock interpolationcounting exponential time hypothesis

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• The complexity of complex weighted Boolean \#CSP
• The complexity of computing the permanent
• The complexity of weighted Boolean \#CSP with mixed signs
• Which problems have strongly exponential complexity?
• Block interpolation: a framework for tight exponential-time counting complexity
• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Complexity of generalized satisfiability counting problems
• The Exponential Time complexity of counting (quantum) graph homomorphisms
• The complexity of counting in sparse, regular, and planar graphs
• On the complexity of \#CSP
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Boolean Holant Problems with Nonnegative Weights
• Complexity Dichotomies for Counting Problems
• Complexity of Counting CSP with Complex Weights
• The complexity of the counting constraint satisfaction problem
• On the complexity of \(k\)-SAT
• A full complexity dichotomy for immanant families
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory

This page was built for publication: Exponential time complexity of the complex weighted Boolean \#CSP

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