archives

An Observation on Probability Randomness with Application to Complexity Classes


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

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.

Full text available as:Postscript
Adobe PDF

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