0
$\begingroup$

It is known that:

  • $\Sigma_2^P \subseteq \Delta_3^P$ i.e. $NP^{NP} \subseteq \Delta_3^P$.
  • $BPP^{NP} \subseteq \Delta_3^P$

If $\Sigma_2^P = PSPACE => BPP^{NP} \subseteq NP^{NP}$

Doesn't that imply: $\Sigma_2^P = PSPACE => BPP \subseteq NP$?

Am I missing something?

$\endgroup$
1
$\begingroup$

I have not verified your claims, but I will still try to answer.

In the general case, given a language $A$ and two complexity classes $\mathcal{C}_1$ and $\mathcal{C}_2$, the equality $\mathcal{C}_1^A = \mathcal{C}_2^A$ does not imply $\mathcal{C}_1 = \mathcal{C}_2$ (and same with inclusion).

In particular, Baker, Gill and Solovay proved in 1975 that there exists two languages $A$ and $B$ such that $\mathsf{P}^A=\mathsf{NP}^A$ and $\mathsf{P}^B\neq \mathsf{NP}^B$ (but it is still not known whether $\mathsf{P} =\mathsf{NP}$ or not). The idea is that giving and oracle to a non-determinist class let that class use this oracle non-deterministicaly, meaning potentially using it independently on every computing path, resulting in virtually calling the oracle an exponential number of times.

That means that $\mathsf{NP}^A \subseteq \mathsf{P}^A$ but it is not necessarily true that $\mathsf{NP}\subseteq \mathsf{P}$.

$\endgroup$
2
  • $\begingroup$ thanks a lot! I understand the general case. But if I understand correctly to show we can't have a proof using an oracle we have to show both cases i.e ($X^a \subseteq Y^a$) and ($X^b \nsubseteq Y^b$). Are we aware of an oracle result that shows: $BPP^a \nsubseteq NP^a$? $\endgroup$ Nov 4 at 11:47
  • $\begingroup$ I don't know about this particular case, sorry. $\endgroup$
    – Nathaniel
    Nov 4 at 11:59

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.