On Approximation Algorithms for # P

Abstract

The theme of this paper is to investigate to what extent approximation, possibly together with randomization, can reduce the complexity of problems in Valiant’s class # P. In general, any function in # P can be approximated to within any constant factor by a function in the class $\Delta _3^p $ of the polynomial-time, hierarchy. Relative to a particular oracle, $\Delta _3^p $ cannot be replaced by $\Delta _2^p $ in this result. Another part of the paper introduces a model of random sampling where the size of a set X is estimated by checking, for various “sample sets” S, whether or not S intersects X For various classes of sample sets, upper and lower bounds on the number of samples required to estimate the size of X are discussed. This type of sampling is motivated by particular problems in # P such as computing the size of a backtrack search tree. In the case of backtrack search trees, a sample amounts to checking whether a certain path exists in the tree. One of the lower bounds suggests that such tests alone are not sufficient to give a polynomial-time approximation algorithm for this problem, even if the algorithm can randomize.