AN OBSERVATION ON PROBABILITY VERSUS RANDOMNESS WITH APPLICATIONS TO COMPLEXITY CLASSES

Every class C of languages satisfying a simple topological condition i s shown to have probability one if and only if it contains some langua ge that is algorithmically random in the sense of Martin-Lof. This res ult 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 character izations lead to results like: P = NP if and only if an algorithmicall y random set exists that is less-than-or-equal-to(btt)P-hard for NP.