Geodesic
On the parameterized complexity of approximate counting
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 2, pp. 197-223

Voir la notice de l'article provenant de la source Numdam

DOI MR   Zbl

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.

DOI : 10.1051/ita/2011007
Classification : 68Q15, 68Q17
Keywords: computational complexity, parameterized complexity, counting problems, approximate counting 
Andrés Montoya, J. On the parameterized complexity of approximate counting. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 2, pp. 197-223. doi: 10.1051/ita/2011007
@article{ITA_2011__45_2_197_0,
     author = {Andr\'es Montoya, J.},
     title = {On the parameterized complexity of approximate counting},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {197--223},
     year = {2011},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {2},
     doi = {10.1051/ita/2011007},
     mrnumber = {2811654},
     zbl = {1234.68121},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011007/}
}
TY  - JOUR
AU  - Andrés Montoya, J.
TI  - On the parameterized complexity of approximate counting
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 197
EP  - 223
VL  - 45
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011007/
DO  - 10.1051/ita/2011007
LA  - en
ID  - ITA_2011__45_2_197_0
ER  - 
%0 Journal Article
%A Andrés Montoya, J.
%T On the parameterized complexity of approximate counting
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 197-223
%V 45
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011007/
%R 10.1051/ita/2011007
%G en
%F ITA_2011__45_2_197_0

Cité par Sources :