Approximation to measurable functions and its relation to probabilistic computation |
| |
Institution: | Department of Computer Science, University of Houston, Houston, TX 77004, USA |
| |
Abstract: | A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|