The complexity of counting problems

MaRDI QIDQ2776272zbMATH OpenFDO

Authors Amy Gale, D. J. A. Welsh

Publication date 9 April 2002

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The relative complexity of approximate counting problems
• scientific article; zbMATH DE number 1072530
• scientific article; zbMATH DE number 1670534
• scientific article; zbMATH DE number 1057883
• Descriptive complexity of \(\#\)P functions

Cited in

(17)

• On the power of enumerative counting
• Query answering over inconsistent knowledge bases: a probabilistic approach
• Discussing the ``big \(n\) problem
• Parameterized counting problems
• Complexity dichotomies of counting problems
• Counting Value Sets: Algorithm and Complexity
• Rényi entropies as a measure of the complexity of counting problems
• The Parameterized Complexity of Counting Problems
• Computational complexity of counting and sampling
• scientific article; zbMATH DE number 850077 (Why is no real title available?)
• scientific article; zbMATH DE number 7075922 (Why is no real title available?)
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
• Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks
• The complexity of the co-occurrence problem
• Picturing Counting Reductions with the ZH-Calculus

This page was built for publication: The complexity of counting problems

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