×

zbMATH — the first resource for mathematics

On the parameterized complexity of approximate counting. (English) Zbl 1234.68121
Summary: 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.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] M. Agrawal, N. Saxena and N. Kayal, PRIMES is in P . Annals of Math.160 (2004) 781-793. · 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. · Zbl 1019.68135 · link.springer.de
[3] R.G. Downey and M.R. Fellows, Parameterized Complexity. Springer-Verlag (1999).
[4] J. Flum and M. Grohe, The parameterized complexity of counting problems. SIAM J. Comput.33 (2004) 892-922. Zbl1105.68042 · Zbl 1105.68042 · doi:10.1137/S0097539703427203
[5] J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag (2006). · Zbl 1143.68016
[6] O. Goldreich, Randomized methods in Computation. Manuscript (2001) oded/rnd.html. URIhttp://www.wisdom.weizmann.ac.il/ · www.wisdom.weizmann.ac.il
[7] C. Lautemann, B P P and the Polynomial Hierarchy. Inform. Process. Lett.17 (1983) 215-217. · Zbl 0515.68042 · doi:10.1016/0020-0190(83)90044-3
[8] J.A. Montoya, On parameterized Counting. Ph.D thesis, Freiburg University (2008). · Zbl 1155.03023 · d-nb.info
[9] J.A. Montoya, The parameterized complexity of probability amplification. Inform. Process. Lett.109 (2008) 46-53. · Zbl 1191.68342 · doi:10.1016/j.ipl.2008.06.007
[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. · Zbl 1154.68433 · doi:10.1007/11847250_5
[11] C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994). · Zbl 0833.68049
[12] L. Stockmeyer, On approximation Algorithms for # P . SIAM J. Comput.14 (1985) 849-861. · Zbl 0589.68031
[13] S. Toda, P P is as hard as the polynomial-time hierarchy. SIAM J. Comput.20 (1991) 865-877. · Zbl 0733.68034 · doi:10.1137/0220053
[14] L.G. Valiant, The complexity of computing the permanent. Theoret. Comput. Sci.8 (1979) 189-201. · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6
[15] L.G. Valiant, The complexity of enumeration and reliability problems. SIAM J. Comput.8 (1979) 410-421. · Zbl 0419.68082 · doi:10.1137/0208032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.