A pseudorandom oracle characterization of BPP

It is known from work of C.H. Bennett and J. Gill (1981) and K. Ambos-Spies (1986) that the following conditions are equivalent: (i) L∈BPP; (ii); for almost all oracles A, l∈P^A. It is shown here that the following conditions are also equivalent to (i) and (ii): (iii) the set of oracles A for which L∈P^A has pspace-measure 1; (iv) for every pspace-random oracle A, L∈P ^A. It follows from this characterization that almost every A∈DSPACE (2^poly) is polynomial-time hard for BPP. Succinctly, the main content of the proof is that pseudorandom generators exist relative to every pseudorandom oracle