6
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\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 Sep 21 '10 at 11:07
  • $\begingroup$ Sorry, how do you add links? $\endgroup$ – slimton Sep 21 '10 at 11:07
  • 1
    $\begingroup$ @slimton: See meta.stackexchange.com/questions/19756/…, under the heading “Comment formatting.” Or you can simply write a URL and it will be converted to a link. $\endgroup$ – Tsuyoshi Ito Sep 21 '10 at 15:15
  • $\begingroup$ @Sadeq: You should definitely update the zoo with the additional references. $\endgroup$ – Joshua Grochow Sep 21 '10 at 15:37
  • 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 Sep 21 '10 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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