Exponential time complexity of the complex weighted Boolean \#CSP

DOI10.1007/978-3-031-49190-0_6MaRDI QIDQ6591459zbMATH OpenFDO

Authors Ying Liu

Publication date 22 August 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49190-0_6

zbMATH Keywords

\#CSPblock interpolationcomputational complexitycounting exponential time hypothesisdichotomypinning

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• A full complexity dichotomy for immanant families
• Complexity Dichotomies for Counting Problems
• Complexity of counting CSP with complex weights
• Complexity of generalized satisfiability counting problems
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Nonnegative weighted \#CSP: an effective complexity dichotomy
• On the complexity of \#CSP
• On the complexity of k-SAT
• The complexity of Boolean Holant problems with nonnegative weights
• The complexity of complex weighted Boolean \#CSP
• The complexity of computing the permanent
• The complexity of counting in sparse, regular, and planar graphs
• The Complexity of Enumeration and Reliability Problems
• The complexity of the counting constraint satisfaction problem
• The Complexity of Weighted Boolean #CSP
• The complexity of weighted Boolean \#CSP with mixed signs
• The Exponential Time complexity of counting (quantum) graph homomorphisms
• Which problems have strongly exponential complexity?

Cited in

(1)

• Sub-exponential time lower bounds for \#VC and \#Matching on 3-regular graphs

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)