1985/11/01 by Larry Stockmeyer · 6 citations
Computer Science · Mathematics · #Machine Learning and Algorithms #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods
paper · doi:10.1137/0214060
openalex publication_date 1985/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/20
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 Δ 3p of the polynomial-time, hierarchy. Relative to a particular oracle, Δ 3p cannot be replaced by Δ 2p 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.