×

zbMATH — the first resource for mathematics

On approximation algorithms for #P. (English) Zbl 0589.68031
It is shown that any function in Valiant’s class #P can be approximated to within any constant factor by a function in the class \(\Delta^ P_ 3\) of the polynomial-time hierarchy. A model of random sampling is introduced and discussed in detail. The paper is of interest to specialists in the theory of algorithmic complexity.
Reviewer: A.V.Anisimov

MSC:
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI