TY - GEN
T1 - On the complexity of real functions
AU - Braverman, Mark
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33646729763&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646729763&partnerID=8YFLogxK
U2 - 10.1109/SFCS.2005.58
DO - 10.1109/SFCS.2005.58
M3 - Conference contribution
AN - SCOPUS:33646729763
SN - 0769524680
SN - 9780769524689
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 155
EP - 164
BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
T2 - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Y2 - 23 October 2005 through 25 October 2005
ER -