

Book, Ronald V., Lutz, Jack H. and Wagner, Klaus W. (1992) An Observation on Probability Randomness with Application to Complexity Classes. Technical Report TR9214, Department of Computer Science, Iowa State University.
Abstract
An Observation on Probability versus Randomness
with Applications to Complexity Classes
Ronald V. Book, Jack H. Lutz, and Klaus W. Wagner
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
MartinLof. This result is used to derive separation properties of
algorithmically random oracles and to give characterizations of the
complexity classes P, BPP, AM, and PH in terms of reducibility to
such oracles. These characterizations lead to results like: P = NP if
and only if there exists an algorithmically random set that is
polynomialtime btthard for NP.
Contact site administrator at: ssg@cs.iastate.edu
