1
$\begingroup$

If a $\mathsf{PSPACE-Complete}$ problem (say $\mathsf{TQBF}$) has an algorithm that has the runtime $\mathsf{NP^{NP}}$ it follows that $\mathsf{PSPACE=\Sigma^P_2}$.

Does that also imply $\mathsf{\Sigma^P_2 = \Pi^p_2}$? Moreover, does that imply $ \mathsf{\Delta^p_2\subset \Sigma^P_2}$ or is that question still open?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Since PSPACE is closed under complementation, if $\mathsf{PSPACE} = \Sigma_2^P$ then $$ \Sigma_2^P = \mathsf{PSPACE} = \mathsf{coPSPACE} = \mathsf{co}\Sigma_2^P = \Pi_2^P. $$ We always have $\Delta_2^P \subseteq \Sigma_2^P$. I'm not sure if you can deduce the opposite inclusion under your assumption.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. I am unclear about the statement: "..opposite inclusion..". If I am correct it means that it cannot tell if the inclusion $\Delta_2^P \subseteq \Sigma_2^P$ is proper or not? $\endgroup$
    – J.Doe
    Commented Oct 29, 2021 at 14:02
  • 1
    $\begingroup$ Given an inclusion $A \subseteq B$, the opposite inclusion is $B \subseteq A$. $\endgroup$
    – Yuval Filmus
    Commented Oct 29, 2021 at 14:03
  • 1
    $\begingroup$ I'm not sure how you would deduce $\Delta_2^P \neq \Sigma_2^P$; for all we know, it could be that P equals NP. $\endgroup$
    – Yuval Filmus
    Commented Oct 29, 2021 at 14:03
  • $\begingroup$ aah I understand. thank a lot. $\endgroup$
    – J.Doe
    Commented Oct 29, 2021 at 14:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.