Type 2 computational complexity of functions on Cantor's space.
Klaus Weihrauch, Christoph Kreitz.
Theoretical Computer Science, 82(1):1-18, 1991.
Abstract
	Continuity and computability on Cantor's space C has turned out to be a very natural basis for a Type 2 theory of effectivity (TTE). In particular, the investigation of Type 2 computational complexity (e.g. complexity in analysis) requires the study of oracle machines which (w.l.g.) operate on Cantor's space. However, no general Type 2 complexity theory has been developed so far. In this paper we lay a foundation for this theory by investigating computational complexity of functions G: C-->{0,1}* and S: C-->C and the related concepts of dependence and input-lookahead. In the former case results of Gordon and Shamir are extended and generalized. For continuous functions S: C-->C the relation between the three concepts is studied in detail. Compact sets are proven to be the natural domains of resource bounded functions on C. Finally, we demonstrate that an optimization of the input-lookahead used by a machine may result in a non-polynomial increase of computation time.

			Back to overview of papers
Bibtex Entry
	@Article{ar:WeihrauchKreitz91a, author = "Klaus Weihrauch and Christoph Kreitz", title = "Type 2 computational complexity of functions on Cantor's space", journal = "Theoretical Computer Science", volume = 82, year = 1991, pages = "1--18", publisher = "Elsevier Science Publishers B.V." }