patternMinor
Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$
Viewed 0 times
mathsfsubseteqproofbpp
Problem
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.
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.
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#118690, answer score: 3
Revisions (0)
No revisions yet.