2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The $\mathsf{NP}^{\mathsf{BPP}}$ machine is not probabilistic at all. $\endgroup$ Dec 19 '19 at 10:13
  • $\begingroup$ @Yuval Filmus Why? $M_{NP^{BPP}}$ uses another Turing machine, which is probabilistic. Hence machine $M_{NP^{BPP}}$ must be probabilistic. $\endgroup$
    – Katy
    Dec 19 '19 at 14:43
  • $\begingroup$ 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. $\endgroup$ Dec 19 '19 at 15:14
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you clarify what exactly do you mean by "The other direction"? are you claiming $NP^{BPP}=BPP^{NP}$? $\endgroup$ Dec 26 '19 at 13:48
  • $\begingroup$ The other direction is "if $x \notin L$, then the machine rejects $x$". $\endgroup$ Dec 26 '19 at 14:28

Your Answer

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

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