On the parameterized complexity of approximate counting

Andrés Montoya, J.

doi:10.1051/ita/2011007

Andrés Montoya, J.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 2, pp. 197-223.

Résumé

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.

MR Zbl

DOI : 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},
     mrnumber = {2811654},
     zbl = {1234.68121},
     language = {en},
     url = {http://archive.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
SP  - 197
EP  - 223
VL  - 45
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2011007/

Bibliographie
Cité par

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

[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 | Zbl

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

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

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

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

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

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

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

[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 | Zbl

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

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

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

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

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

Cité par Sources :