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?

$\endgroup$
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.

$\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
    Oct 29 at 14:02
  • 1
    $\begingroup$ Given an inclusion $A \subseteq B$, the opposite inclusion is $B \subseteq A$. $\endgroup$ Oct 29 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$ Oct 29 at 14:03
  • $\begingroup$ aah I understand. thank a lot. $\endgroup$
    – J.Doe
    Oct 29 at 14:06

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.