On Low for Speed Oracles

Bienvenu, Laurent; Downey, Rodney

doi:10.4230/LIPIcs.STACS.2018.15

File

LIPIcs.STACS.2018.15.pdf

Filesize: 0.51 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2018.15
URN: urn:nbn:de:0030-drops-85226

Author Details

Laurent Bienvenu

Rodney Downey

Cite AsGet BibTex

Laurent Bienvenu and Rodney Downey. On Low for Speed Oracles. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.STACS.2018.15

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.

Keywords

Lowness for speed
Oracle computations
Turing degrees

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Eric Allender, Harry Buhrman, and Michal Koucký. What can be efficiently reduced to the Kolmogorov-random strings? Annals of Pure and Applied Logic, 138:2-19, 2006.
Eric Allender, Luke Friedman, and William I. Gasarch. Limits on the computational power of random strings. Information and Computation, 222:80-92, 2013.
Theodore Baker, John Gill, and Robert Solovay. Relativizations of the 𝒫 = ?NP question. SIAM Journal on Computing, 4(4):431-442, 1975.
Robertson Bayer. Lowness For Computational Speed. PhD thesis, University of California Berkeley, 2012.
Laurent Bienvenu. Game-theoretic characterizations of randomness: unpredictability and stochasticity. PhD thesis, Université de Provence, 2008. https://tel.archives-ouvertes.fr/tel-00332425v2.
Manuel Blum. On effective procedures for speeding up algorithms. Journal of the ACM, 18(290-305), 1971.
Mingzhong Cai, Rodney Downey, Rachel Epstein, Steffen Lempp, and Joseph Miller. Random strings and tt-degrees of Turing complete c.e. sets. Logical Methods in Computer Science, 10(3), 2014.
Rodney Downey and Denis Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, 2010.
Christine A. Haught. The degrees below a 1-generic degree < 0'. Journal of Symbolic Logic, 51, 1986.
Carl Jockusch. Degrees of generic sets. In Frank Drake and Stanley S. Wainer, editors, Recursion theory: its generalizations and applications, number 45 in London Mathematical Society Lecture Note Series, pages 110-139. Cambridge Unversity Press, 1980.
Steven M. Kautz. Degrees of random sets. PhD thesis, Cornell University, 1991.
Dexter Kozen. Theory of Computation. Springer, New York, 2006.
Stuart Kurtz. Randomness and genericity in the degrees of unsolvability. PhD dissertation, University of Illinois at Urbana, 1981.
André Nies. Computability and randomness. Oxford Logic Guides. Oxford University Press, 2009.
Gerald Sacks. On the degrees less than 0'. Annals of Mathematics, 77:211-231, 1963.
Robert Soare. Turing Computability: Theory and Applications. Theory and Applications of Computability. Springer, 2016.