Type 2 computational complexity of functions on Cantor's space

DOI10.1016/0304-3975(91)90168-2zbMath0725.03043OpenAlexW2070180583MaRDI QIDQ2277260

Christoph Kreitz, Weihrauch, Klaus

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90168-2

zbMATH Keywords

computabilitycomplexity in analysisContinuityoracle machinesType 2 theory of effectivityCantor's spaceinput-lookaheadType 2 computational complexity

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Higher-type and set recursion theory (03D65)

Related Items

Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations, On the complexity of online computations of real functions, Computability on computable metric spaces, Feasible real random access machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computation of recursive functionals using minimal initial segments
• Type 2 recursion theory
• Theory of representations
• Compactness in constructive analysis revisited
• Representations of the real numbers and of the open subsets of the set of real numbers
• Computational complexity of real functions
• Theorie der Numerierungen I
• Fast Multiple-Precision Evaluation of Elementary Functions