On the parameterized complexity of approximate counting
Escuela de Matemáticas, Universidad industrial de Santander, Spain;
Accepted: 1 February 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.
Mathematics Subject Classification: 68Q15 / 68Q17
Key words: Computational complexity / parameterized complexity / counting problems / approximate counting
© EDP Sciences, 2011