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

DOI10.1007/S00224-009-9182-XzbMATH Open1185.68331OpenAlexW2169321137MaRDI QIDQ733754FDOQ733754

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

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

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)

Cites Work

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

Cited In (4)

• Type-two polynomial-time and restricted lookahead
• A tight relationship between generic oracles and type-2 complexity theory
• Speed-Up Theorems in Type-2 Computation
• 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)