A pseudorandom oracle characterization of BPP
Jack H. Lutz · 2002
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 in BPP; (ii); for almost all oracles A, l in P/sup 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 in P/sup A/ has pspace-measure 1; (iv) for every pspace-random oracle A, L in P/sup A/. It follows from this characterization that almost every A in DSPACE (2/sup poly/) is polynomial-time hard for BPP. Succinctly, the main content of the proof is that pseudorandom generators exist relative to every pseudorandom oracle.>