On low for speed oracles

DOI10.1016/j.jcss.2019.08.007zbMath1459.03060arXiv1712.09710OpenAlexW2974919271MaRDI QIDQ2009647

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

oracle computationslowness for speed

Mathematics Subject Classification ID

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

Related Items (1)

A MINIMAL SET LOW FOR SPEED

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A non-inversion theorem for the jump operator
• Limits on the computational power of random strings
• Theory of computation.
• What can be efficiently reduced to the Kolmogorov-random strings?
• On the degrees less than 0'
• Turing Computability
• Random strings and tt-degrees of Turing complete C.E. sets
• Algorithmic Randomness and Complexity
• A jump class of noncappable degrees
• A fixed-point-free minimal degree
• The degrees below a 1-generic degree < 0′
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Effective Procedures for Speeding Up Algorithms
• Randomness, relativization and Turing degrees

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