Computational Complexity of Real Functions

In this chapter we introduce the formal definitions of computational complexity of real functions. We first review the definitions of computable real numbers and computable real functions and their basic properties. Then, the oracle Turing machine is introduced as the formal model for computing real functions. This model allows us to define the complexity measures for computing real functions in a natural way. The class of polynomial time computable real functions is then defined, and several characterizations of this class will be given. Other complexity classes of real numbers and real functions, such as NP real functions and log-space computable real functions, will be defined in later chapters.