On low for speed oracles

DOI10.1016/J.JCSS.2019.08.007MaRDI QIDQ2009647zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Rodney G. Downey

Publication date 29 November 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.09710

zbMATH Keywords

lowness for speedoracle computations

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by lowness notions from computability theory, Allender introduced the concept of "low for speed" oracles. An oracle A is low for speed if relativizing to A has essentially no effect on computational complexity, meaning that if a decidable language can be decided in time $f(n)$ with access to oracle A, then it can be decided in time poly(f(n)) without any oracle. The existence of non-computable such A's was later proven by Bayer and Slaman, who even constructed a computably enumerable one, and exhibited a number of properties of these oracles as well as interesting connections with computability theory. In this paper, we pursue this line of research, answering the questions left by Bayer and Slaman and give further evidence that the structure of the class of low for speed oracles is a very rich one.

Recommendations

• scientific article; zbMATH DE number 4011939
• On one application of computations with oracle
• On the complexity of speed scaling
• A MINIMAL SET LOW FOR SPEED
• scientific article; zbMATH DE number 3883613
• Oracles with costs
• scientific article; zbMATH DE number 512846
• Some results on speed-up
• Separating the low and high hierarchies by oracles

Cites work

• A fixed-point-free minimal degree
• A jump class of noncappable degrees
• A non-inversion theorem for the jump operator
• Algorithmic randomness and complexity.
• Computability and randomness
• scientific article; zbMATH DE number 4135927 (Why is no real title available?)
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 3715539 (Why is no real title available?)
• Limits on the computational power of random strings
• On Effective Procedures for Speeding Up Algorithms
• On the degrees less than 0'
• Random strings and truth-table degrees of Turing complete c.e. sets
• Randomness, relativization and Turing degrees
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• The degrees below a 1-generic degree < 0′
• Theory of computation.
• Turing computability. Theory and applications
• What can be efficiently reduced to the Kolmogorov-random strings?

Cited in

(2)

• On low for speed oracles
• A MINIMAL SET LOW FOR SPEED

This page was built for publication: On low for speed oracles

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