<p>We know that <span class="math-container">$\mathsf{BPP}$</span> is in <span class="math-container">$\mathsf{\Sigma^P_2\cap \Pi^P_2}$</span> by Sipser-Lautemann, as this proof relativizes we can get <span class="math-container">$\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$</span>, but are there any result improving on this?</p>
<p>For several related class (e.g. <span class="math-container">$\mathsf{ZPP^{NP}}$</span>) we know we don't have to increase the order of the polynomial hierarchy for containment (<span class="math-container">$\mathsf{ZPP^{NP}\subseteq \Sigma^P_2\cap \Pi^P_2}$</span>). Are there similar results for <span class="math-container">$\mathsf{BPP^{NP}}$</span>?</p>

CC BY-SA 4.0
2024-04-12T09:20:15.190Z
I’m pretty sure nothing is known about the inclusion of $\mathrm{BPP^{NP}}$ in other classes other than what you get by relativizing the corresponding results for BPP with an NP-complete oracle. So, e.g., $\mathrm{BPP=ZPP^{promiseRP}}$ yields $\mathrm{BPP^{NP}=ZPP^{promiseRP^{NP}}}$.
Emil Jeřábek
CC BY-SA 4.0
2024-04-12T09:23:25.647Z
Note that the inclusion for ZPP *is*, similarly, increased by one level: we have $\mathrm{ZPP\subseteq NP\cap coNP}$, which relativizes to $\mathrm{ZPP^{NP}\subseteq NP^{NP}\cap coNP^{NP}=\Sigma^P_2\cap\Pi^P_2}$.
Emil Jeřábek
CC BY-SA 4.0
2024-04-13T04:52:04.707Z
@Marsh Does not seem to be. https://www.math.ucdavis.edu/~greg/zoology/diagram.xml
Tayfun Pay
CC BY-SA 4.0
2024-04-14T21:26:37.540Z
In the OQ: also for AM! (in only the second level of PH)
Joshua Grochow
<cc.complexity-theory><complexity-classes>
Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?
Marshall
# Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

(Asked by: username_0 on 2024-04-12)

We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P\_2\cap \Pi^P\_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P\_3\cap \Pi^P\_3}$, but are there any result improving on this?

For several related class (e.g. $\mathsf{ZPP^{NP}}$) we know we don't have to increase the order of the polynomial hierarchy for containment ($\mathsf{ZPP^{NP}\subseteq \Sigma^P\_2\cap \Pi^P\_2}$). Are there similar results for $\mathsf{BPP^{NP}}$?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: I’m pretty sure nothing is known about the inclusion of $\mathrm{BPP^{NP}}$ in other classes other than what you get by relativizing the corresponding results for BPP with an NP-complete oracle. So, e.g., $\mathrm{BPP=ZPP^{promiseRP}}$ yields $\mathrm{BPP^{NP}=ZPP^{promiseRP^{NP}}}$.  
> **username_1**: Note that the inclusion for ZPP *is*, similarly, increased by one level: we have $\mathrm{ZPP\subseteq NP\cap coNP}$, which relativizes to $\mathrm{ZPP^{NP}\subseteq NP^{NP}\cap coNP^{NP}=\Sigma^P_2\cap\Pi^P_2}$.  
> **username_2**: @Marsh Does not seem to be. https://www.math.ucdavis.edu/~greg/zoology/diagram.xml  
> **username_3**: In the OQ: also for AM! (in only the second level of PH)  

---

## 0 answers

