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.

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $#W\left[P\right]$, 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 : https://doi.org/10.1051/ita/2011007
Classification : 68Q15,  68Q17
Mots clés : computational complexity, parameterized complexity, counting problems, approximate counting
@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},
zbl = {1234.68121},
mrnumber = {2811654},
language = {en},
url = {http://www.numdam.org/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
DA  - 2011///
SP  - 197
EP  - 223
VL  - 45
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011007/
UR  - https://zbmath.org/?q=an%3A1234.68121
UR  - https://www.ams.org/mathscinet-getitem?mr=2811654
UR  - https://doi.org/10.1051/ita/2011007
DO  - 10.1051/ita/2011007
LA  - en
ID  - ITA_2011__45_2_197_0
ER  - 
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. http://www.numdam.org/articles/10.1051/ita/2011007/

[1] M. Agrawal, N. Saxena and N. Kayal, PRIMES is in $P.$ Annals of Math. 160 (2004) 781-793. | MR 2123939 | Zbl 1071.11070

[2] V. Arvind and V. Raman, Approximation algorithms for some parameterized counting problems, in Proceedings of the 13th Annual International Symposium on Algorithms and Computation, edited by P. Bose and P. Morin. Lect. Notes Comput. Sci. 2518 (2002) 453-464. | MR 2079050 | Zbl 1019.68135

[3] R.G. Downey and M.R. Fellows, Parameterized Complexity. Springer-Verlag (1999). | MR 1656112 | Zbl 0914.68076

[4] J. Flum and M. Grohe, The parameterized complexity of counting problems. SIAM J. Comput. 33 (2004) 892-922. | MR 2065338 | Zbl 1105.68042

[5] J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag (2006). | MR 2238686 | Zbl 1143.68016

[6] O. Goldreich, Randomized methods in Computation. Manuscript (2001) http://www.wisdom.weizmann.ac.il/ oded/rnd.html.

[7] C. Lautemann, $BPP$ and the Polynomial Hierarchy. Inform. Process. Lett. 17 (1983) 215-217. | MR 742072 | Zbl 0515.68042

[8] J.A. Montoya, On parameterized Counting. Ph.D thesis, Freiburg University (2008). | Zbl 1155.03023

[9] J.A. Montoya, The parameterized complexity of probability amplification. Inform. Process. Lett. 109 (2008) 46-53. | MR 2466791 | Zbl 1191.68342

[10] M. Muller, Randomized approximations of parameterized counting problems. Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06). Lect. Notes Comput. Sci. 4169 (2006) 50-59. | MR 2333272 | Zbl 1154.68433

[11] C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994). | MR 1251285 | Zbl 0833.68049

[12] L. Stockmeyer, On approximation Algorithms for $#P.$ SIAM J. Comput. 14 (1985) 849-861. | MR 807886 | Zbl 0589.68031

[13] S. Toda, $PP$ is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20 (1991) 865-877. | MR 1115655 | Zbl 0733.68034

[14] L.G. Valiant, The complexity of computing the permanent. Theoret. Comput. Sci. 8 (1979) 189-201. | MR 526203 | Zbl 0415.68008

[15] L.G. Valiant, The complexity of enumeration and reliability problems. SIAM J. Comput. 8 (1979) 410-421. | MR 539258 | Zbl 0419.68082

Cité par Sources :