Rationally presented metric spaces and complexity, the case of the space of uniformly continuous real functions on a compact interval

2025/02/19 by Lombardi, Henri, Labhalla, Salah, Moutai, E.
#03F60 #54C35 #54E35 #68Q55 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2502.13768

Abstract

We define the notion of \em rational presentation of a complete metric space in order to study metric spaces from the algorithmic complexity point of view. In this setting, we study some presentations of the space \czu of uniformly continuous real functions over [0,1] with the usual norm: \normef_∞ = \bf Sup \ \absf(x) ; 0 ≤ x ≤ 1\. This allows us to have a comparison of a global kind between complexity notions attached to these presentations. In particular, we get a generalisation of Hoover's results concerning the \sl Weierstrass approximation theorem in polynomial time. We get also a generalisation of previous results on analytic functions which are computable in polynomial time.

Related

• Bounded time computation on metric spaces and Banach spaces
• Nearly Computable Real Numbers
• Decomposition complexity with respect to coarse properties
• Representation Theory of Compact Metric Spaces and Computational Complexity of Continuous Data
• Computability and Complexity over the Product Topology of Real Numbers