<p>I would write this as a comment, but there was a limitation on the number of characters. So I'll put it here.</p>
<p>The paper title is &quot;<a href="https://doi.org/10.1007/BF01744434" rel="nofollow noreferrer">Relativized Polynomial Hierarchies Extending Two Levels</a>.&quot; 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 <a href="https://scholar.google.com/scholar?cites=4173642586326142804&amp;as_sdt=2005&amp;sciodt=2000&amp;hl=en" rel="nofollow noreferrer">Google Scholar</a> and <a href="https://www.google.com/search?q=%22Relativized%20polynomial%20hierarchies%20extending%20two%20levels%22&amp;um=1&amp;ie=UTF-8&amp;hl=en&amp;tbo=u&amp;tbs=bks:1&amp;gws_rd=ssl" rel="nofollow noreferrer">Google Books</a>.</p>
<p>The Complexity Zoo attributes the proof that &quot;There exist oracles relative to which EXP = NP = ZPP&quot; to this paper. Yet this is <em>incomplete</em>, since other references cite the following papers as well [off-topic: I updated Zoo to cover the new references as well]:</p>
<ol>
<li>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
<li>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
</ol>
<p>There's also the following paper:</p>
<ul>
<li> 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
</ul>
<p>cited by several references as having influence on the relativized ZPP = EXP result (see for instance &quot;<a href="https://www.computer.org/csdl/proceedings-article/ccc/2001/10530028/12OmNBhpRZw" rel="nofollow noreferrer">Comparing Notions of Full Derandomization</a>&quot; by Lance Fortnow).</p>
<p>Specially, while the paper you cited only proves the existence of an oracle <span class="math-container">$B$</span> such that</p>
<p><span class="math-container">${(\Sigma _1^p)^B} \subset {(\Sigma _2^p)^B} = (\Pi _2^B)$</span>,</p>
<p>The paper #1 above continues by proving:</p>
<p><span class="math-container">${(\Sigma _2^p)^B} = (\Pi _2^B) = \mathbf{EXP}^B = \mathbf{NEXP}^B$</span></p>
<p>and paper #2 above completes it by showing the relations between relatizied <strong>EXP</strong> and (if I'm not mistaken) <strong>RP</strong>.</p>
<p>Joining forces, the relativized <strong>BPP</strong> = <strong>NEXP</strong> is deduced.</p>
<p>PS: Please provide me with an email address of yours. I want to send you some docs.</p>

CC BY-SA 2.5
2010-09-21T11:07:13.207Z
The ZPP entry of the <a ref="http://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.
slimton
CC BY-SA 2.5
2010-09-21T15:41:40.363Z
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.
slimton
CC BY-SA 2.5
2010-09-21T16:59:06.763Z
@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.
Sadeq Dousti
CC BY-SA 4.0
2010-09-21T10:50:36.380Z
2022-11-09T13:02:31.353Z
2022-11-09T13:02:31.353Z
Sadeq Dousti
<p>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.</p>

<cc.complexity-theory><complexity-classes><oracles><relativization>
Oracle relative to which BPP = EXP
slimton
# Oracle relative to which BPP = EXP

(Asked by: username_0 on 2010-09-21)

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.

**Tags:** cc.complexity-theory, complexity-classes, oracles, relativization


---

## 1 answers

### Answer by username_1 on 2010-09-21. Score: 9 | Accepted answer

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](https://doi.org/10.1007/BF01744434)." 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](https://scholar.google.com/scholar?cites=4173642586326142804&as_sdt=2005&sciodt=2000&hl=en) and [Google Books](https://www.google.com/search?q=%22Relativized%20polynomial%20hierarchies%20extending%20two%20levels%22&um=1&ie=UTF-8&hl=en&tbo=u&tbs=bks:1&gws_rd=ssl).

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- 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](https://www.computer.org/csdl/proceedings-article/ccc/2001/10530028/12OmNBhpRZw)" 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.

> **Comments:**
> **username_0**: The ZPP entry of the <a ref="http://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.  
> **username_0**: 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.  
> **username_1**: @Joshua: Sure thing! @username_0: 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.  

---

