Type 2 computational complexity of functions on Cantor's space.


Klaus Weihrauch, Christoph Kreitz.  
Theoretical Computer Science, 82(1):118, 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
inputlookahead. 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 inputlookahead used by a machine may result in a nonpolynomial
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 = "118", publisher = "Elsevier Science Publishers B.V." } 