Approximation to measurable functions and its relation to probabilistic computation (Q1088659)

This paper is one of a sequence of papers by the author and H. Friedman on computational complexity of real functions. The basic notion of computational complexity of continuous real functions is developed by the author and \textit{H. Friedman} [Theor. Comput. Sci. 20, 323-352 (1982; Zbl 0498.03047)]. The paper under review deals with computational complexity in measure theory and complexity of integration. It first extends the notion of recursively measurable sets, as defined by \textit{G. Kreisel} and \textit{D. Lacombe} [C. R. Acad. Sci., Paris 245, 1106-1109 (1957; Zbl 0079.009)] and \textit{N. A. Shanin} [Tr. Mat. Inst. Steklova 67, 15-294 (1962; Zbl 0113.008)], to define the class of polynomial-time approximable (or, polynomial-time measurable) sets and polynomial-time approximable real functions. One of the main results shows an interesting relationship between polynomial-time approximability and randomized algorithms which have been developed in the context of the NP-completeness theory. It is shown that the Lebesgue integrals of polynomial-time approximable functions are always polynomial-time computable if and only if \(FP=\#P\). This is a generalization of \textit{H. Friedman}'s [Adv. Math. 53, 80-98 (1984; Zbl 0563.03023)] result on the computational complexity of the Riemann integration of polynomial-time computable functions.