No label defined (Q4249729)

Computability and complexity in analysis (called CCA) is an important research area which applies the well-developed techniques from discrete computability and complexity theory to study the continuous problems from classical mathematics and other areas. This paper is a very good survey about the main topics of CCA. The first part of the paper discusses the computability in analysis. After introducing the computation model, several important results about the computable reals and real functions are discussed, including the roots of computable real functions, the solutions of ordinary differential equations and the computable linear operators. The second part covers the complexity theory in analysis. A quite reasonable complexity measure for real numbers and real functions is introduced. After recalling the basic notions of discrete complexity theory, a lot of numerical problems are classified according to their complexity in terms of discrete complexity classes. These problems include the maximization problem, the root-finding problem, the integration problem, ordinary differential equations and integral equations. At last, several approaches to study the computational complexity of continuous problems are briefly discussed and compared. For the entire collection see [Zbl 0905.03002].