Measure and Integration
Ker‐I Ko · Birkhäuser Boston eBooks · 1991
The notion of the measurability of a set S of real numbers may be viewed as the approximability to set S by simple measurable open sets. Using this computational viewpoint, we may define a recursively measurable set to be one that can be approximated by simple open sets such that the measures of the approximation errors converge to zero recursively. A polynomial-time measurable set, or, more appropriately, a polynomial-time approximable set then is one for which the measures of the approximation errors converge to zero in a polynomial rate. Similarly, we may define a polynomial-time approximable function to be one that can be approximated by simple step functions with errors converging to zero in a polynomial rate. This class of real functions contains noncontinuous functions and hence properly contains the class of polynomial-time computable functions defined in Chapter 2. However, if we restrict our attention to the class of continuous functions which have polynomial moduli of continuity, then it is not known whether the notion of polynomial-time approximability is strictly stronger than the notion of polynomial-time computability. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.