Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T21:44:07.293Z Has data issue: false hasContentIssue false
  • English
  • Français

On the parameterized complexity of approximate counting

Published online by Cambridge University Press:  18 April 2011

J. Andrés Montoya
J. Andrés Montoya*
Affiliation:
Escuela de Matemáticas, Universidad industrial de Santander, Spain; [email protected]; [email protected]
Get access

Abstract

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.

Keywords

Computational complexityparameterized complexitycounting problemsapproximate counting
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 2 , April 2011 , pp. 197 - 223
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

M. Agrawal, N. Saxena and N. Kayal, PRIMES is in $P.$ Annals of Math. 160 (2004) 781–793.
Arvind, V. and Raman, V., 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. CrossRef
R.G. Downey and M.R. Fellows, Parameterized Complexity. Springer-Verlag (1999).
Flum, J. and Grohe, M., The parameterized complexity of counting problems. SIAM J. Comput. 33 (2004) 892–922. CrossRef
J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag (2006).
O. Goldreich, Randomized methods in Computation. Manuscript (2001) http://www.wisdom.weizmann.ac.il/ oded/rnd.html.
Lautemann, C., $BPP$ and the Polynomial Hierarchy. Inform. Process. Lett. 17 (1983) 215–217. CrossRef
J.A. Montoya, On parameterized Counting. Ph.D thesis, Freiburg University (2008).
Montoya, J.A., The parameterized complexity of probability amplification. Inform. Process. Lett. 109 (2008) 46–53. CrossRef
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.
C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994).
L. Stockmeyer, On approximation Algorithms for $\#P.$ SIAM J. Comput. 14 (1985) 849–861.
Toda, S., $PP$ is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20 (1991) 865–877. CrossRef
Valiant, L.G., The complexity of computing the permanent. Theoret. Comput. Sci. 8 (1979) 189–201. CrossRef
Valiant, L.G., The complexity of enumeration and reliability problems. SIAM J. Comput. 8 (1979) 410–421. CrossRef