Bounded time computation on metric spaces and Banach spaces

zbMATH Open1452.03099arXiv1701.02274MaRDI QIDQ5144686FDOQ5144686

Authors: Florian Steinberg, Matthias Schröder 

Publication date: 19 January 2021

Abstract: We extend the framework by Kawamura and Cook for investigating computational complexity for operators occurring in analysis. This model is based on second-order complexity theory for functions on the Baire space, which is lifted to metric spaces by means of representations. Time is measured in terms of the length of the input encodings and the required output precision. We propose the notions of a complete representation and of a regular representation. We show that complete representations ensure that any computable function has a time bound. Regular representations generalize Kawamura and Cook's more restrictive notion of a second-order representation, while still guaranteeing fast computability of the length of the encodings. Applying these notions, we investigate the relationship between purely metric properties of a metric space and the existence of a representation such that the metric is computable within bounded time. We show that a bound on the running time of the metric can be straightforwardly translated into size bounds of compact subsets of the metric space. Conversely, for compact spaces and for Banach spaces we construct a family of admissible, complete, regular representations that allow for fast computation of the metric and provide short encodings. Here it is necessary to trade the time bound off against the length of encodings.

Full work available at URL: https://arxiv.org/abs/1701.02274

Recommendations

• Computational complexity on computable metric spaces
• Complexity theory of (functions on) compact metric spaces
• Complexity theory for spaces of integrable functions
• Rational presented metric spaces and complexity, the case of the space of real functions uniformly continuous on a compact interval
• Computable Banach spaces via domain theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computation over the reals, computable analysis (03D78) Metric spaces, metrizability (54E35) Complexity of computation (including implicit computational complexity) (03D15) Normed linear spaces and Banach spaces; Banach lattices (46B99)

Cited In (5)

• Parametrised second-order complexity theory with applications to the study of interval computation
• Complexity theory of (functions on) compact metric spaces
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Quantitative continuity and Computable Analysis in Coq
• Computational complexity on computable metric spaces

This page was built for publication: Bounded time computation on metric spaces and Banach spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144686)