Why is $BPP^{NP}$ in the polynomial hierarchy? I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. However, how does that imply $BPP^{NP}$ is inside the polynomial hierarchy?


closed as off-topic by Emil Jeřábek, Aryeh, Gamow, Hsien-Chih Chang 張顯之, domotorp May 8 at 7:17

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Aryeh, Gamow, Hsien-Chih Chang 張顯之, domotorp
If this question can be reworded to fit the rules in the help center, please edit the question.


$BPP\subset PH$ does NOT imply that $BPP^{NP}\subset PH$. You have to go through the proof of $BPP\subset PH$ and notice that it relativizes, i.e., also holds if the Turing-machines have access to an oracle.

  • $\begingroup$ are you saying that by checking the proof, I am able to see that $BPP^{NP}\in(NP^{NP})^{NP}$ something like that? Thanks! $(NP^{NP})^{NP}$ seems to just be $NP^{NP}$ since the last oracle seems to be redundant? $\endgroup$ – Herman Chu May 7 at 19:25
  • 1
    $\begingroup$ These are not really research level questions, so maybe you should rather ask them at cs.stackexchange.com. $\endgroup$ – domotorp May 8 at 7:17

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