Rationally presented metric spaces and complexity - The spaces of uniformly continuous real functions over a compact interval

We define the notion of rational presentation of a complete metric space, i n order to study metric spaces from the algorithmic complexity point of vie w. In this setting, we study some representations of the space C[0, 1] of u niformly continuous real functions over [0, 1] with the usual norm: \\f\\(i nfinity) = Sup{\f(x)\; 0 less than or equal to x less than or equal to 1}. This allows us to have a comparison of global kind between complexity notio ns attached to these presentations. In particular, we get a generalization of Hoover's results concerning the Weierstrass approximation theorem in pol ynomial time. We get also a generalization of previous results on analytic functions which are computable in polynomial time. (C) 2001 Elsevier Scienc e B.V. All rights reserved.