Article contents
On the parameterized complexity of approximate counting
Published online by Cambridge University Press: 18 April 2011
Abstract
In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $\#W[P]$, the parameterized analogue of $\#P$. We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2011
References
- 2
- Cited by