The Computational Complexity of Measurable Functions and Sets

This paper steps beyond a standard overview of classical measure and integration theory to set a new framework for the constructive study of measurable functions and sets. It makes a trailblazing contribution by officially bringing concepts from complexity and computability theory into the analysis of continuous analysis, and doing so by developing "recursively approximable sets" and "polynomial-time approximable functions." These definitions give fundamental questions of measurability and approximation a new, computationally based perspective. The work uncovers a profound and unexpected relationship between the two disciplines, showing a set to be recursively approximable if and only if it is recursively measurable (Theorem 21). Its strongest but most unexplored result is a negative result (Theorem 24), establishing the existence of a straightforward recursive function whose level set fails to be recursively approximable. This result is as strong as a fundamental open problem of discrete complexity theory and yields new insight into the interface between continuous and discrete computation. The results of the prework form the basis of a new area of computable analysis, and it paves the way for further research areas such as an axiomatic approach to computational complexity on Banach spaces and L*-spaces and a complete characterization of recursive functions in terms of the approximability of their level sets.