An oracle construction relative to which BPP = EXP is usually attributed to Heller (Mathematical System Theory Vol. 17, 1984). Unfortunately I don't have the paper available in my library. Could someone explain how it goes? If it is easier to give an oracle where NP = EXP that would fine already.
Oracle relative to which BPP = EXP
cc.complexity theory;complexity classes;oracles;relativization
I would write this as a comment, but there was a limitation on the number of characters. So I'll put it here.The paper title is Relativized Polynomial Hierarchies Extending Two Levels. When you do not have access to an article, your best bet is to search for books/articles that reference your indented paper. The best place, IMO, is Google Scholar and Google Books.The Complexity Zoo attributes the proof that There exist oracles relative to which EXP = NP = ZPP to this paper. Yet this is incomplete, since other references cite the following papers as well [off-topic: I updated Zoo to cover the new references as well]:Heller, H. 1984. On relativized polynomial and exponential computations. SIAM J. Comput. 13, 4 (Nov. 1984), 717-725. DOI= http://dx.doi.org/10.1137/0213045Heller, H. 1986. On relativized exponential and probabilistic complexity classes. Inf. Control 71, 3 (Dec. 1986), 231-243. DOI= http://dx.doi.org/10.1016/S0019-9958(86)80012-2There's also the following paper: Kurtz, S. A. 1985. Sparse sets in NP-P: relativizations. SIAM J. Comput. 14, 1 (Feb. 1985), 113-119. DOI= http://dx.doi.org/10.1137/0214008cited by several references as having influence on the relativized ZPP = EXP result (see for instance Comparing Notions of Full Derandomization by Lance Fortnow).Specially, while the paper you cited only proves the existence of an oracle $B$ such that${(\Sigma _1^p)^B} \subset {(\Sigma _2^p)^B} = (\Pi _2^B)$,The paper #1 above continues by proving:${(\Sigma _2^p)^B} = (\Pi _2^B) = \mathbf{EXP}^B = \mathbf{NEXP}^B$and paper #2 above completes it by showing the relations between relatizied EXP and (if I'm not mistaken) RP.Joining forces, the relativized BPP = NEXP is deduced.PS: Please provide me with an email address of yours. I want to send you some docs.