Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.13768 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918128093495296 |
|---|---|
| author | Lombardi, Henri Labhalla, Salah Moutai, E. |
| author_facet | Lombardi, Henri Labhalla, Salah Moutai, E. |
| contents | 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: $\norme{f}_{\infty} = {\bf Sup} \{ \abs{f(x)} ; \;0 \leq x \leq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13768 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rationally presented metric spaces and complexity, the case of the space of uniformly continuous real functions on a compact interval Lombardi, Henri Labhalla, Salah Moutai, E. Numerical Analysis 68Q55, 03F60, 54C35, 54E35 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: $\norme{f}_{\infty} = {\bf Sup} \{ \abs{f(x)} ; \;0 \leq x \leq 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. |
| title | Rationally presented metric spaces and complexity, the case of the space of uniformly continuous real functions on a compact interval |
| topic | Numerical Analysis 68Q55, 03F60, 54C35, 54E35 |
| url | https://arxiv.org/abs/2502.13768 |