Speed-up theorems in type-2 computations using oracle Turing machines

DOI10.1007/S00224-009-9182-XMaRDI QIDQ733754zbMATH OpenOpenAlexFDO

Authors Chung-Chih Li

Publication date 19 October 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-009-9182-x

zbMATH Keywords

oracle Turing machinespeed-up theoremtype-2 computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Higher-type and set recursion theory (03D65)

Recommendations

• Speed-Up Theorems in Type-2 Computation
• scientific article; zbMATH DE number 1735623
• Type 2 computational complexity of functions on Cantor's space
• On low for speed oracles

Cites work

• scientific article; zbMATH DE number 3655922 (Why is no real title available?)
• scientific article; zbMATH DE number 3700811 (Why is no real title available?)
• scientific article; zbMATH DE number 65741 (Why is no real title available?)
• scientific article; zbMATH DE number 108365 (Why is no real title available?)
• scientific article; zbMATH DE number 3507951 (Why is no real title available?)
• scientific article; zbMATH DE number 1142310 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A new Characterization of Type-2 Feasibility
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computational speed-up by effective operators
• On Effective Procedures for Speeding Up Algorithms
• On the Computational Complexity of Algorithms
• Recursion on the countable functionals
• Recursive Functionals and Quantifiers of Finite Types I
• Recursive Functionals and Quantifiers of Finite Types II
• Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
• Simple quadratures in the complex plane
• The Mathematical Work of S.C.Kleene
• Theories of computational complexity
• Turing-Machine Computable Functionals of Finite Types II^†

Cited in

(3)

• Speed-Up Theorems in Type-2 Computation
• A tight relationship between generic oracles and type-2 complexity theory
• A speed-up theorem without tape compression

This page was built for publication: Speed-up theorems in type-2 computations using oracle Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733754)