# Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$

How to show that $$\mathbf{NP}^{BPP} \subseteq \mathbf{BPP}^{NP}$$?

I tried to build $$NTM$$ $$M_{NP1}$$, which uses $$PTM$$ $$M_{BPP1}$$. Show that there will always be $$PTM$$ $$M_{BPP2}$$, which uses $$L (NTM$$ $$M_{NP2})$$ as the oracle language and repeats the actions of $$NTM$$ $$M_{NP1}$$ with the oracle $$L (PTM$$ $$M_{BPP1})$$. Unfortunately, I could not do this. It turns out that the $$NTM$$ output that uses $$PTM$$ will also happen with some probability?

Hope You can help me to show it.

• The $\mathsf{NP}^{\mathsf{BPP}}$ machine is not probabilistic at all. Dec 19 '19 at 10:13
• @Yuval Filmus Why? $M_{NP^{BPP}}$ uses another Turing machine, which is probabilistic. Hence machine $M_{NP^{BPP}}$ must be probabilistic.
– Katy
Dec 19 '19 at 14:43
• It is an $\mathsf{NP}$ machine with an access to a $\mathsf{BPP}$ oracle. So it's just a nondeterministic oracle Turing machine, whose oracle calls correspond to languages in $\mathsf{BPP}$. If $\mathsf{P} = \mathsf{BPP}$, then this is the same as $\mathsf{NP}^{\mathsf{P}} = \mathsf{NP}$, which everybody can agree is not probabilistic in any way. Dec 19 '19 at 15:14

Suppose that $$M$$ is a machine in $$\mathsf{NP}^\mathsf{BPP}$$ accepting some language $$L$$. We can think of $$M$$ as accepting an input $$x$$ and a witness $$y$$. The machine $$M$$ runs a polytime algorithm, and has oracle access to $$\mathsf{BPP}$$. We can further assume that the witness contains, for each oracle call to $$\mathsf{BPP}$$, both the input and the output — the witness might be longer, but it still has polynomial length. Denoting the pairs by $$z_i,w_i$$ and the $$\mathsf{BPP}$$ languages by $$L_i$$, we thus deduce that there is a polytime machine $$A$$ such that $$x \in L \Leftrightarrow \exists y,\vec{z},\vec{w},\vec{L} \; A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i L_i(z_i) = w_i,$$ where the quantification is over polynomial length strings. (We elide the issue of how $$L_i$$ is represented.)
Suppose furthermore that $$L_i$$ is computed by some $$\mathsf{BPP}$$ machine $$A_i$$ with small error probability. We can think of $$A_i$$ as accepting two inputs: the actual input $$z_i$$, and a randomness string $$r_i$$.
This suggests the following $$\mathsf{BPP}^\mathsf{NP}$$ machine for $$L$$. The machine gets input $$x$$ and randomness string $$\vec{r}$$. Using a single oracle call to $$\mathsf{NP}$$, it checks whether there exist $$y,\vec{z},\vec{w},\vec{L}$$ such that $$A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i A_i(z_i,r_i) = w_i.$$
If $$x \in L$$, let $$y,\vec{z},\vec{w},\vec{L}$$ the $$M$$-witness for it. For the vast majority of randomness strings $$\vec{r}$$, we will have $$A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i A_i(z_i,r_i) = w_i,$$ and so our machine will accept $$x$$.
The other direction is a bit more subtle, and I'll let you work it out carefully. It requires the $$\mathsf{BPP}$$ machines to have really small error, which can be achieved via repetition.
• Can you clarify what exactly do you mean by "The other direction"? are you claiming $NP^{BPP}=BPP^{NP}$? Dec 26 '19 at 13:48
• The other direction is "if $x \notin L$, then the machine rejects $x$". Dec 26 '19 at 14:28