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}}$?

  • 1
    $\begingroup$ 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}}}$. $\endgroup$ Apr 12 at 9:20
  • 1
    $\begingroup$ 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}$. $\endgroup$ Apr 12 at 9:23
  • $\begingroup$ @Marsh Does not seem to be. math.ucdavis.edu/~greg/zoology/diagram.xml $\endgroup$
    – Tayfun Pay
    Apr 13 at 4:52
  • $\begingroup$ In the OQ: also for AM! (in only the second level of PH) $\endgroup$ Apr 14 at 21:26


Your Answer

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