Computational complexity on computable metric spaces

Mathematical Logic Quarterly 49 (1):3-21 (2003)

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a generally infinite family of numbers looks straightforward, at first glance, examples for which this maximum exists seem to be very rare. It is the main purpose of this paper to prove that, nevertheless, the definition has a large number of important applications. Using the framework of TTE [40], we introduce computable metric spaces and computability on the compact subsets. We prove that every computable metric space has a c-proper c-admissible representation. We prove that Turing machine time complexity of a function computable relative to c-admissible c-proper representations has a computable bound on every computable compact subset. We prove that computably compact computable metric spaces have concise c-proper c-admissible representations and show by examples that many canonical representations are of this kind. Finally, we compare our definition with a similar one by Labhalla et al. [22]. Several examples illustrate the concepts. By these results natural and realistic definitions of computational complexity are now available for a variety of numerical problems such as image processing, integration, continuous Fourier transform or wave propagation
Keywords computable metric space  Computational complexity  admissible representation
Categories (categorize this paper)
DOI 10.1002/malq.200310001
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,179
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Closed Choice and a Uniform Low Basis Theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.

Add more citations

Similar books and articles

Computable Metrization.Tanja Grubba, Matthias Schröder & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4‐5):381-395.
Borel Complexity and Computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.
Complexity of Admissible Rules.Emil Jeřábek - 2007 - Archive for Mathematical Logic 46 (2):73-92.
How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
Compact Metric Spaces and Weak Forms of the Axiom of Choice.E. Tachtsis & K. Keremedis - 2001 - Mathematical Logic Quarterly 47 (1):117-128.
Computation and Automata.Arto Salomaa - 1985 - Cambridge University Press.
Computability of Measurable Sets Via Effective Topologies.Yongcheng Wu & Decheng Ding - 2005 - Archive for Mathematical Logic 45 (3):365-379.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.


Added to PP index

Total views
10 ( #772,914 of 2,285,433 )

Recent downloads (6 months)
1 ( #841,072 of 2,285,433 )

How can I increase my downloads?


My notes

Sign in to use this feature