A Pseudorandom Oracle Characterization of BPP
| Author(s) : | Jack H. Lutz Jack H. Lutz, |
| Publisher : | N/A |
| Publication Date : | 1993 |
| ISSN : | N/A |
| Abstract : | It is known from work of Bennett and Gill and Ambos-Spies that the following conditions are equivalent. (i) L 2 BPP. (ii) For almost all oracles A, L 2 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 2 P A has pspace-measure 1. (iv) For every pspace-random oracle A, L 2 P A, |