Disclaimer: If not interested in my background, skip directly to the question below!

I am a complete newbie when it comes to complexity theory. I come from a physics background and I am currently working through the complexity-theoretical arguments behind Boson sampling and and other quantum supremacy proposals. These rely crucially on the Conjecture, that the Polynomial Hierarchy does not collapse to its third level.

The small piece of the argument, I am concerned with is the following:

Theorem 1: If $P^{\#P}=BPP^{NP}$ then the PH collapses to its third level, i.e. $PH=\Sigma_3$.

What I know:

  1. By Toda's Theorem, $PH\subseteq P^{\#P}$, thus to prove Theorem 1, it would suffice to show that $BPP^{NP}\subseteq \Sigma_3$.

  2. I have also found out (and seen proofs of) that $BPP\subseteq \Sigma_2$.

To me it looks like, that because of $BPP\subseteq \Sigma_2$, it should be true that $BPP^{NP}\subseteq \Sigma_2^{NP}$. Now, if $\Sigma_2^{NP}$ was the same as $NP^{\Sigma_2}=\Sigma_3$, I would be done proving Theorem 1.

Question: It is true, though? i.e. is

$$ \left(NP^{NP}\right)^{NP} \overset{?}{=}NP^{\left(NP^{NP}\right)}$$

and does the ordering of the parentheses in these oracle constructions matter? If it is not, I would be grateful, if someone could point out, how to prove Theorem 1.

  • $\begingroup$ The OP has a genuine concern since his bg is not complexity. It is rude the community votes to close the post rather than guiding. $\endgroup$ – Bread Winner Sep 4 '19 at 11:24
  • $\begingroup$ any guidance is highly appreciated, I understand this is probably very basic $\endgroup$ – Marsl Sep 4 '19 at 11:56
  • $\begingroup$ ah, you see, I did not know this. Is there anyway to move the post there? Otherwise, I should close and repost?! $\endgroup$ – Marsl Sep 4 '19 at 14:01
  • $\begingroup$ You can flag the post for moderator attention and ask for it to be migrated, but since there are no answers, it is easier if you just delete the post here and repost it there. $\endgroup$ – Emil Jeřábek Sep 4 '19 at 14:52
  • 2
    $\begingroup$ This has actually already been asked here: cstheory.stackexchange.com/questions/972/…. $\endgroup$ – Huck Bennett Sep 4 '19 at 15:27

Your Answer

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

Browse other questions tagged or ask your own question.