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)

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

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)