Type 2 computational complexity of functions on Cantor's space (Q2277260): Difference between revisions

Continuity and computability on Cantor's space \({\mathbb{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 \(\Gamma: {\mathbb{C}}\to \{0,1\}^*\) and \(\Sigma: {\mathbb{C}}\to {\mathbb{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 \(\Sigma: {\mathbb{C}}\to {\mathbb{C}}\) the relation between the three concepts is studied in detail. Compact sets are proved to be natural domains of resource bounded functions on \({\mathbb{C}}\). Finally, we demonstrate that an optimization of the input-lookahead used by a machine may result in a rapid increase of computation time.