Book, Ronald V., Lutz, Jack H. and Wagner, Klaus W. (1992) An Observation on Probability Randomness with Application to Complexity Classes. Technical Report TR92-14, Department of Computer Science, Iowa State University.
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
Martin-Lof. 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
polynomial-time btt-hard for NP.
Contact site administrator at: email@example.com