Abstract
Every class C of languages satisfying a simple topological condition is shown to have probability one if and only if it contains some language that is algorithmically random in the sense of Martin-Löf. This result is used to derive separation properties of algorithmically random oracles and to give characterizations of the complexity classesP, BPP, AM, andPH in terms of reducibility to such oracles. These characterizations lead to results like:P =NP if and only if an algorithmically random set exists that is ≤ P btt -hard forNP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Ambos-Spies. Randomness, relativations, and polynomial reducibilities.Proc. First Conf. on Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223, Springer-Verlag, Berlin, 1986, pp. 23–34.
J. Balcázar, R. Book, and U. Schöning. The polynomial-time hierarchy and sparse oracles.J. Assoc. Comput. Mach., 33:603–617, 1986.
J. Balcázar, J. Díaz, and J. Gabarró.Structural Complexity I. Springer-Verlag, Berlin, 1988.
J. Balcázar, J. Díaz, and J. Gabarró.Structural Complexity II. Springer-Verlag, Berlin, 1990.
C. Bennett. Logical depth and physical complexity. InThe Universal Turing Machine: A Half-Century Survey (R. Herken, ed.), Oxford University Press, Oxford, 1988, pp. 227–257.
C. Bennett and J. Gill. Relative to a random oracleP itA ≠ NPitA ≠ co-NPitA with probability 1.SIAM J. Comput., 10:96–113, 1981.
J.-Y. Cai. Probability one separation of the boolean hierarchy.Proc. STACS 87, Lecture Notes in Computer Science, Vol. 38, Springer-Verlag, Berlin, 1987, pp. 148–158.
J.-Y. Cai. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy.J. Comput. System Sci., 38:68–85, 1989.
R. Karp and R. Lipton. Turing machines, that take advice.Enseign. Math. (2), 28:191–209, 1982.
S. Kautz. Degrees of random sets. Ph.D. dissertation, Cornell University, 1991.
T. Long and A. Selman. Relativizing complexity classes with sparse oracles.J. Assoc. Comput. Mach., 33:618–627, 1986.
P. Martin-Löf. On the definition of random sequences.Inform. and Control, 9:602–619, 1966.
P. Martin-Löf. Complexity oscillations in infinite binary sequences.Z. Wahrsch. Verw. Gebiete, 19:225–230, 1971.
N. Nisan and A. Wigderson. Hardness versus randomness.Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 2–11.
M. Ogiwara and A. Lozano. On one query self-reducible sets.Proc. 6th IEEE Conf. on Structure in Complexity Theory, 1991, pp. 139–151.
M. Ogiwara and O. Watanabe. On polynomial bounded truth table reducibility of NP sets to sparse sets.SIAM J. Comput., 20:471–183, 1991.
H. Rogers.Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
S. Tang and R. Book. Polynomial-time reducibilities and “almost-all” oracle sets.Theoret. Comput. Sci., 81:36–47, 1991.
Author information
Authors and Affiliations
Additional information
The work of the first author was supported in part by the Alexander-von-Humboldt-Stiftung and by the National Science Foundation under Grant CCR-8913584 while he visited the Lehrstuhl für Theoretische Informatik, Institut für Informatik, Universität Würzburg, Germany. The work of the second author was supported in part by the National Science Foundation under Grant CCR-8809238 and in part by DIMACS, where he was a visitor while a portion of his work was done.
Rights and permissions
About this article
Cite this article
Book, R.V., Lutz, J.H. & Wagner, K.W. An observation on probability versus randomness with applications to complexity classes. Math. Systems Theory 27, 201–209 (1994). https://doi.org/10.1007/BF01578842
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01578842