An Observation on Probability Randomness with Application to Complexity Classes

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.

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
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.


Subjects:
All uncategorized technical reports


ID code:
00000020
Deposited by:
Staff Account on 01 May 1992





Contact site administrator at: ssg@cs.iastate.edu