Abstract
It is shown that, for every k≥0 and every fixed algorithmically random language B, there is a language that is polynomialtime, truth-table reducible in k+1 queries to B but not truth-table reducible in k queries in any amount of time to any algorithmically random language C. In particular, this yields the separation Pk-tt(RAND) ⫋ P(k+1)-tt(RAND), where RAND is the set of all algorithmically random languages.
This research was supported in part by National Science Foundation Grant CCR-8913584.
This research, was supported in part by National Science Foundation Grant CCR-9157382, with matching funds from Rockwell International and Microware Systems Corporation.
This research was carried out while the third author was at Iowa State University.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. L. Balcázar, J. Díaz, and J. Gabarró, Structural Complexity I, Springer-Verlag, 1988.
R. Book and K.-I Ko, On sets truth-table reducible to sparse sets, SIAM Journal on Computing 17 (1988), pp. 903–919.
R. V. Book, Additional queries and algorithmically random languages, In K. Ambos-Spies, S. Homer, and U. Schöning, editors, Complexity Theory. Cambridge University Press, 1993, to appear.
R. V. Book, J. H. Lutz, and K. Wagner, An observation on probability versus randomness with applications to complexity classes, Mathematical Systems Theory (1993), to appear.
G. J. Chaitin, A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery 22 (1975), pp. 329–340.
G. J. Chaitin, Incompleteness theorems for random reals, Advances in Applied Mathematics 8 (1987), pp. 119–146.
D. G. Champernowne, Construction of decimals normal in the scale of ten, J. London Math. Soc. 2 (1933), pp. 254–260.
T. Hagerup and C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters 33 (1990), pp. 305–308.
Donald E. Knuth, The Art of Computer Programming, volume 2, Addison-Wesley, 1966.
A. N. Kolmogorov and V. A. Uspenskii, Algorithms and randomness, translated in Theory of Probability and its Applications 32 (1987), pp. 389–412.
L. A. Levin, On the notion of a random sequence, Soviet Mathematics Doklady 14 (1973), pp. 1413–1416.
J. H. Lutz, Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences 44 (1992), pp. 220–258.
P. Martin-Löf, On the definition of random sequences, Information and Control 9 (1966), pp. 602–619.
E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50 (1944), pp. 284–316.
C. P. Schnorr, Process complexity and effective random tests, Journal of Computer and System Sciences 7 (1973), pp. 376–388.
A. Kh. Shen', The frequency approach to the definition of a random sequence, Semiotika i Informatika (1982), pp. 14–42, in Russian.
A. Kh. Shen', On relations between different algorithmic definitions of randomness, Soviet Mathematics Doklady 38 (1989), pp. 316–319.
R. M. Solovay, 1975, reported in [6].
S. Tang and R. Book, Polynomial-time reducibilities and “almost-all” oracle sets, Theoretical Computer Science 81 (1991), pp. 35–47.
M. van Lambalgen, Random Sequences, PhD thesis, Department of Mathematics, University of Amsterdam, 1987.
M. van Lambalgen, Von Mises' definition of random sequences reconsidered, Journal of Symbolic Logic 52 (1987), pp. 725–755.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Book, R.V., Lutz, J.H., Martin, D.M. (1994). The global power of additional queries to random oracles. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds) STACS 94. STACS 1994. Lecture Notes in Computer Science, vol 775. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57785-8_158
Download citation
DOI: https://doi.org/10.1007/3-540-57785-8_158
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57785-0
Online ISBN: 978-3-540-48332-8
eBook Packages: Springer Book Archive