-1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

$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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '19 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 '19 at 7:17

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