Why is $BPP^{NP}$ in the polynomial hierarchy? I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. Should I just simply reuse the proof of $BPP\subset NP^{NP}$, feed in each machine an oracle solving 3SAT problem, and show that $BPP^{NP}\subset NP^{NP^{NP}}$? Is it because normally, the proof in complexity theory can be easily relativized by an oracle?

  • 1
    $\begingroup$ Have you tried following your suggested proof technique? $\endgroup$ – Yuval Filmus May 8 '19 at 11:49
  • 1
    $\begingroup$ You already got advice on how to prove it: cstheory.stackexchange.com/a/43843/5038. domotorp suggested exactly this. Now it sounds to me like you're coming here to ask "should I do what I was advised to do?". Well, I would think a reasonable answer is "yes, give it a try and see what happens, probably they had a reason to suggest that; and then if you run into some specific step where you get stuck, ask about that step". Have I misunderstood the situation? $\endgroup$ – D.W. May 8 '19 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.