Voir la notice de l'article provenant de la source Numdam
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.
@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},
publisher = {EDP-Sciences},
volume = {45},
number = {2},
year = {2011},
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
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
Cité par Sources :