$P^{NP}\subseteq BPP^{NP}$ holds. According to current knowledge $BPP$ is in $\Sigma_2^P\cap\Pi_2^P$ holds. So according to current knowledge is following true?

  1. $P^{\Sigma_2^P\cup\Pi_2^P}\subseteq BPP^{NP}\subseteq(\Sigma_2^P\cap\Pi_2^P)^{NP}\subseteq\Sigma_3^P\cap\Pi_3^P$?

  2. Is $P^{\Sigma_2^P\cup\Pi_2^P}$ the largest standard polynomial hierarchy class in $BPP^{NP}$ and is $(\Sigma_2^P\cap\Pi_2^P)^{NP}$ the smallest standard polynomial hierarchy class containing $BPP^{NP}$?

  • $\begingroup$ How is $(\Sigma_2^\mathrm{P} \cap \Pi_2^\mathrm{P})^{\mathbf{NP}}$ defined? Note relativized classes only make sense if you start out with a class which has a machine characterization (and AFAIK $\Sigma_2^\mathrm{P} \cap \Pi_2^\mathrm{P}$ is not one such class). $\endgroup$ – dkaeae May 27 '19 at 7:59
  • $\begingroup$ @dkaeae I thought $NP\cap coNP$ had a machine charaterization and likewise.. no? $\endgroup$ – T.... May 27 '19 at 8:05
  • 1
    $\begingroup$ Well, we have $\mathbf{NP} \cap \mathbf{coNP} = \mathbf{P}^{\mathbf{NP} \cap \mathbf{coNP}}$, but I'm unsure how you'd make the oracles "stack". $\endgroup$ – dkaeae May 27 '19 at 8:10
  • $\begingroup$ @dkaeae I see.... $\endgroup$ – T.... May 27 '19 at 8:12
  • $\begingroup$ @dkaee we know $BPP$ is in $\Sigma_2^P\cap\Pi_2^P$. What is the best way to say where $BPP^{NP}$ is properly best contained in (I thought it was $(\Sigma_2^P\cap\Pi_2^P)^{NP}$ and you have shot it down then)? $\endgroup$ – T.... May 27 '19 at 8:17

The NP-machine hypothesis implies that $BPP^{NP}=P^{NP}$.

So combining with the hypothesis that $PH$ does not collapse, this will falsify the proposition that $P^{\Sigma_2^p\cup\Pi_2^p}\subseteq BPP^{NP}$.

Reference for NP-machine hypothesis and its aforementioned consequence: https://www.researchgate.net/publication/225526797_Hardness_Hypotheses_Derandomization_and_Circuit_Complexity


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.