Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T11:35:55.203Z 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; amontoyaa@googlemail.com; juamonto@uis.edu.co

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we study the parameterized complexity of approximating theparameterized counting problems contained in the class $\#W[P]$,the parameterized analogue of $\#P$. We prove a parameterized analogue of afamous theorem of Stockmeyer claiming that approximate counting belongs tothe second level of the polynomial hierarchy.

Keywords

Computational complexityparameterized complexitycountingproblemsapproximate counting

Information

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

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