<p><a href="https://core.ac.uk/download/pdf/82186689.pdf" rel="noreferrer">Heller</a> gives a relativized world where $BPP = EXP^{NP}$ which sits far outside of $P^{NP}$. Showing $BPP \neq EXP^{NP}$ unconditionally would in itself be considered a major breakthrough in derandomization. </p>

CC BY-SA 4.0
2019-02-23T22:03:09.617Z
What would $BPP\neq EXP^{NP}$ or $BPP\subseteq P^{NP}$ give in terms of lower bounds?
Turbo
CC BY-SA 4.0
2018-08-25T14:05:37.780Z
2018-08-25T14:05:37.780Z
Lance Fortnow
<p>Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?</p>

CC BY-SA 4.0
2018-08-08T11:31:54.577Z
No, it’s not known. However, $\mathrm{BPP\subseteq MA\subseteq S_2P\subseteq ZPP^{NP}}$.
Emil Jeřábek
CC BY-SA 4.0
2018-08-10T08:39:21.717Z
Looks like an answer to me.
Auberon
<cc.complexity-theory><complexity-classes>
Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
Alexey Milovanov
# Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

(Asked by: username_0 on 2018-08-08)

Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

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

> **Comments:**
> **username_1**: No, it’s not known. However, $\mathrm{BPP\subseteq MA\subseteq S_2P\subseteq ZPP^{NP}}$.  
> **username_2**: Looks like an answer to me.  

---

## 1 answers

### Answer by username_3 on 2018-08-25. Score: 9

[Heller](https://core.ac.uk/download/pdf/82186689.pdf) gives a relativized world where $BPP = EXP^{NP}$ which sits far outside of $P^{NP}$. Showing $BPP \neq EXP^{NP}$ unconditionally would in itself be considered a major breakthrough in derandomization.

> **Comments:**
> **username_4**: What would $BPP\neq EXP^{NP}$ or $BPP\subseteq P^{NP}$ give in terms of lower bounds?  

---

