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$
    – Turbo
    Sep 4, 2019 at 11:24
  • $\begingroup$ any guidance is highly appreciated, I understand this is probably very basic $\endgroup$
    – Marsl
    Sep 4, 2019 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, 2019 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$ Sep 4, 2019 at 14:52
  • 2
    $\begingroup$ This has actually already been asked here: cstheory.stackexchange.com/questions/972/…. $\endgroup$ Sep 4, 2019 at 15:27


Your Answer

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

Browse other questions tagged or ask your own question.