Type 2 computational complexity of functions on Cantor's space
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.
- scientific article; zbMATH DE number 1223632
- Type‐2 computability on spaces of integrable functions
- scientific article; zbMATH DE number 65741
- Spaces allowing Type‐2 Complexity Theory revisited
- scientific article; zbMATH DE number 66471
- Complexity theory of (functions on) compact metric spaces
- Complexity theory for spaces of integrable functions
- On total functions, existence theorems and computational complexity
- Computational complexity on computable metric spaces
- On the structure of the space of complexity partial functions
- Compactness in constructive analysis revisited
- Computation of recursive functionals using minimal initial segments
- Computational complexity of real functions
- Fast Multiple-Precision Evaluation of Elementary Functions
- scientific article; zbMATH DE number 3987247 (Why is no real title available?)
- scientific article; zbMATH DE number 4023258 (Why is no real title available?)
- scientific article; zbMATH DE number 4051615 (Why is no real title available?)
- scientific article; zbMATH DE number 4070894 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3788601 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Representations of the real numbers and of the open subsets of the set of real numbers
- Theorie der Numerierungen I
- Theory of representations
- Type 2 recursion theory
- On the complexity of online computations of real functions
- Feasible real random access machines
- Computability on computable metric spaces
- Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
- Conservatively approximable functions
- Complexity theory of (functions on) compact metric spaces
- scientific article; zbMATH DE number 2163039 (Why is no real title available?)
- Resource-bounded continuity and sequentiality for type-two functionals
- Feasible real random access machines
- Speed-up theorems in type-2 computations using oracle Turing machines
This page was built for publication: Type 2 computational complexity of functions on Cantor's space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277260)
