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.


1 Answer 1


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]:

  1. 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/0213045
  2. Heller, 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-2

There'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/0214008

cited 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.

  • $\begingroup$ The ZPP entry of the <a ref="qwiki.stanford.edu/wiki/Complexity_Zoo">complexity zoo</a> points to Heller's paper (the one you link to) as giving an oracle relative to which ZPP = EXP (and hence BPP = EXP too). I've seen other references to this paper for the same claim. $\endgroup$
    – slimton
    Commented Sep 21, 2010 at 11:07
  • 1
    $\begingroup$ There's a more direct route. It turns out that the SIAMJC paper above (which I didn't know of and which is available in my library) contains an oracle construction relative to which NP = EXP (Theorem 6 in that paper). The proof is simple enough that I see how to extend it to an oracle relative to which BPP = EXP. So this answers my question. $\endgroup$
    – slimton
    Commented Sep 21, 2010 at 15:41
  • $\begingroup$ @Joshua: Sure thing! @slimton: I was justifying how the paper cited by you influenced the BPP = EXP, though as you pointed, the definite result appeared in the SIAMJC paper. $\endgroup$ Commented Sep 21, 2010 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.