Type 2 computational complexity of functions on Cantor's space

DOI10.1016/0304-3975(91)90168-2MaRDI QIDQ2277260zbMATH OpenOpenAlexFDO

Authors Christoph Kreitz, Klaus Weihrauch

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

Cantor's spacecomplexity in analysiscomputabilityContinuityinput-lookaheadoracle machinesType 2 computational complexityType 2 theory of effectivity

Mathematics Subject Classification ID

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

Recommendations

• 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

Cites work

• 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

Cited in

(10)

• 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)