0
$\begingroup$
  1. Does $BPP^{NP}\subseteq\Sigma_k^P\cap P/poly^{NP}\subseteq BPP^{\oplus P}$ hold at some $3\leq k<\infty$?

  2. Also is $BPP^{BPP^{\oplus P}}\subseteq BPP^{\oplus P}$ known?

Note Sipser gives $BPP\subseteq \Sigma_2P$ and Adleman gives $BPP\subseteq P/poly$ and so I am tempted to say $k=3$ in $1.$ works. I am not sure relativization plays here.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Adelman's theorem relativizes, i.e. for every oracle $O$ we have $\mathsf{BPP^O\subseteq P/Poly^O}$. To see why you have to go over the proof of Adelman's theorem. The proof goes through showing that given a probabilistic machine with exponentially low error probability, there exists a sequence of coin tosses which produces the correct answer for all (fixed length) inputs. This remains true in the relativized world, use that coin sequence as the advice, and query the oracle whenever necessary while simulating the probabilistic machine with the coins given in the advice.

Additionally, $\mathsf{BPP^{\Sigma_i}}\subseteq \Sigma_{i+3}$. Again, you have to examine the details in the proof of $\mathsf{BPP\subseteq\Sigma_2}$. Suppose $L\in\mathsf{BPP^{\Sigma_i}}$, and $M$ is an oracle probabilistic Turing machine for $L$ with exponentially low error probability. You can use the same idea from $\mathsf{BPP\subseteq\Sigma_2}$, and claim that if $x\in L$ then the set of coin sequences who lead $M$ to accept is big, and in that case it can cover $\{0,1\}^m$ with a small number of shifts, where $m=poly(|x|)$ is the amount of coins used. Similarly, if $x\notin L$ you claim that the set of accepting coin sequences is small and cannot cover $\{0,1\}^m$ with a small number of shifts. All this remains true in the relativized world, as you only reasoned about the "BPP part" of $M$, i.e how it behaves with different coin tosses depending on whether or not the input is in $L$.

What's different is that when you find yourself in need to say "some vector $r\in\{0,1\}^m$ is obtained by shifting an accepting sequence", the part verifying that a sequence is indeed accepting will add additional $i+1$ quantifiers to the formula, after the initial two who talk about space shifting. To be more clear, your final formula has the form:

"$x\in L$ iff there exist shifts such that every vector $r\in\{0,1\}^m$ is obtained by performing one of those shifts on an accepting coin sequence for $x$", this is equivalent to:

"$x\in L$ iff there exists shifts such that every vector $r\in\{0,1\}^m$ can be shifted to generate an accepting coin sequence for $x$". Saying some vector $v$ is an accepting coin sequence requires expressing "$M$ accepts $v$" where $M$ is a poly time machine with access to a $\Sigma_i$ oracle. You can express this using a $\Sigma_{i+1}$ formula (this is analogous to $\mathsf{P^{\Sigma_i}\subseteq \Sigma_{i+1}}$).

The above shows that $\mathsf{BPP^{NP}\subseteq \Sigma_4\cap P/Poly^{NP}}$. As for your second question, I don't know if there are complete problems for $\mathsf{BPP^{\oplus P}}$, so this might make the class $\mathsf{BPP^{BPP^{\oplus P}}}$ ill defined. One interpretation is asking whether the containment holds for every oracle in that class. I doubt this is known, but no obvious important/terrible implication comes to mind. Note that disproving this containment is out of the question, as it would immediately imply $P\neq \oplus P$.

$\endgroup$
8
  • $\begingroup$ Is it because $BPP$ has no complete problems that $BPP^{\oplus P}$ has none? Or is there another reason? $\endgroup$
    – Turbo
    Commented Nov 17, 2017 at 4:41
  • $\begingroup$ Could you clarify "One interpretation is asking whether the containment holds for every oracle in that class"? $\endgroup$
    – Turbo
    Commented Nov 17, 2017 at 4:41
  • $\begingroup$ As for complete problems for $\mathsf{BPP^{\oplus P}}$, I simply meant that I don't know any. Probably, you would run into similar barriers as when trying to find a complete problem for $\mathsf{BPP}$, but there is no direct implication (even if we knew of complete problems for $\mathsf{BPP}$, they might not be complete in the relativized world). $\endgroup$
    – Ariel
    Commented Nov 17, 2017 at 10:07
  • $\begingroup$ "One interpretation is asking whether the containment holds for every oracle in that class" - I meant that you can read your question as "is it true that for all $L\in\mathsf{BPP^{\oplus P}}$ it holds that $\mathsf{BPP^L\subseteq BPP^{\oplus P}}$". $\endgroup$
    – Ariel
    Commented Nov 17, 2017 at 10:07
  • $\begingroup$ Would you know if $PP\subseteq coNP^{BPP}$ then 1. $PP\subseteq NP^{BPP}$ and 2. $PP\subseteq PH$ holds? $\endgroup$
    – Turbo
    Commented Nov 19, 2017 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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