On Low for Speed Oracles

DOI10.4230/LIPIcs.STACS.2018.15zbMath1459.03061OpenAlexW2964001602MaRDI QIDQ3304109

Laurent Bienvenu, Rodney G. Downey

Publication date: 5 August 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.STACS.2018.15

zbMATH Keywords

Turing degreesoracle computationslowness for speed

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Algorithmic Randomness and Complexity
• The degrees below a 1-generic degree < 0′
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Effective Procedures for Speeding Up Algorithms

This page was built for publication: On Low for Speed Oracles