On the Complexity of Real Functions
Mark Braverman · 2005
We establish a new connection between the two most common traditions in the theory of real computation, the Blum-Shub-Smale model and the computable analysis approach. We then use the connection to develop a notion of computability and complexity of functions over the reals that can be viewed as an extension of both models. We argue that this notion is very natural when one tries to determine just how difficult a certain function is for a very rich class of functions.