Assuming if $PSPACE$ collapses to the class $NP^{NP}$ $\mathsf{\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P = PSPACE}$.

Since $\mathsf{NP\subseteq NP^{NP}}$ and $\mathsf{BQP\subseteq QMA \subseteq PSPACE} \implies \mathsf{BQP\subseteq NP^{NP}}$.

Now, by definition:

$NP$ - class of languages verifiable in Polynomial time on a Non-Deterministic Turing machine.

$BQP$ - class of languages solvable in Polynomial time on a Quantum Computer.

Query: Does the above collapse implies any new relation (since none is currently known as of today) b/w the classes $NP$ and $BQP$ since now both belong to the same class $NP^{NP}$?

  • $\begingroup$ I am baffalled at people in general seem to downvote the question without giving any indication why on this forum.. its very discouraging to even gather the will to ask a question here.. $\endgroup$
    – J.Doe
    Sep 19 at 16:13
  • 1
    $\begingroup$ I think people on this forum are sick and tired of questions of the form “if class $X$ collapsed to class $Y$, what would it mean for class $Z$?” They virtually never have any nonobvious answer. And, there’s a troll user who’s asked dozens of such things, exhausting everyone’s patience. $\endgroup$ Sep 19 at 19:28
  • $\begingroup$ @J.Doe I am baffled but usually such collapse, if you state with oracles (which I think is meaningless and superficial yet glorified and popularized as important evidence for class separations by the community as a whole), would hold water at the site. $\endgroup$
    – Mr.
    Sep 20 at 14:49

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.