On the parameterized complexity of approximate counting
J. Andrés Montoya · RAIRO - Theoretical Informatics and Applications · 2011
In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class , the parameterized analogue of . We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.