Polynomial time computable real functions

Abstract. In this paper, we study computability and complexity of real functions. We extend these notions, already defined for functions over closed intervals or over the real line to functions over particular real open sets and give some results and characterizations, especially for polynomial time computable functions. Our representation of real numbers as sequences of rational numbers allows us to implement real functions in a stream language. We give a notion of second order polynomial interpretation for this language to guarantee polynomial time complexity.