On the parameterized complexity of approximate counting
Andrés Montoya, J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011), p. 197-223 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2011-01-01
DOI : https://doi.org/10.1051/ita/2011007
Classification:  68Q15,  68Q17 
@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},
     volume = {45},
     year = {2011},
     pages = {197-223},
     doi = {10.1051/ita/2011007},
     mrnumber = {2811654},
     zbl = {1234.68121},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 197-223. doi : 10.1051/ita/2011007. http://gdmltest.u-ga.fr/item/ITA_2011__45_2_197_0/

[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