# What would be the consequences of PH=PSPACE?

A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing plenty of reasons to believe $NP\neq PSPACE$.

What would be the consequences of the somewhat less dramatic collapse $PH=PSPACE$?

• Am I the only person bored with the surge of "Consequences of $A=B$" questions these days? Granted, they can lead to interesting answers, but the question should at least ask for unexpected, surprising, etc. consequences. – Sylvain Feb 21 '14 at 17:23
• @Sylvain: some of those are actually old questions that have risen from the dead because I added the "conditional-results" tag to them. You can then choose to ignore that tag to make such questions less visible to you. – András Salamon Feb 21 '14 at 17:54

$\mathsf{PH}$ collapses. A $\mathsf{PSPACE}$-complete problem must be in some level of $\mathsf{PH}$, say it's in $\mathsf{\Sigma_k P}$. Since it's $\mathsf{PSPACE}$-complete$=\mathsf{PH}$-complete (by assumption), $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$.

• Isn't ${\bf PSPACE}$ closed under complement and low for itself? That is ${\bf PSPACE}$ = ${\bf PSPACE}^{\bf PSPACE}$ So wouldn't that imply ${\bf NP} = {\bf CoNP}$ and ${\bf NP} ={\bf PSPACE}$? – Tayfun Pay Feb 21 '14 at 19:51
• @TayfunPay : $\:$ I don't see how such an implication could be shown. $\;\;\;\;$ – user6973 Feb 22 '14 at 0:52
• @TayfunPay: Note that $\mathsf{PH}$ - when considered as the single class defined by alternating poly-time TM's with $O(1)$ alternations - is also closed under complement and self-low (even without assuming it's equal to $\mathsf{PSPACE}$). – Joshua Grochow Feb 22 '14 at 20:55
• @JoshuaGrochow Doesn't the existence of a PH-Complete imply that ${\bf PH}$ collapses? I remember something like this being in the old Papadimitriou book. I will check it out tonight. – Tayfun Pay Feb 23 '14 at 23:13
• @TayfunPay: Yes, using the same proof as in my answer (but that doesn't, and seemingly can't, say what level it collapses to under that assumption). – Joshua Grochow Feb 24 '14 at 4:48

It would still imply major separations of complexity classes. For example, $\mathrm{LOGSPACE \neq NP}$ would follow. (If $\mathrm{LOGSPACE = NP}$ then $\mathrm{LOGSPACE = PH}$.)

Also $\mathrm{NP \subseteq P/poly}$ would imply $\mathrm{PSPACE = \Sigma_2 P}$ by Karp-Lipton. It follows that $\mathrm{NP}$ has polysize circuits if and only if $\mathrm{PSPACE}$ does. And of course, we'd have $\mathrm{P = NP}$ iff $\mathrm{P = PSPACE}$. In any case, the consequences of solving $\mathrm{NP}$ problems efficiently would be significantly increased.

• In fact, even NL≠NP follows because $NP^{NL\cap co-NL}=NP$. – domotorp Oct 18 '18 at 20:41

As the answers point out, $PH=PSPACE$ would still have significant consequences, even though not as numerous and dramatic ones as $NP=PSPACE$.

Turning the issue on its head, it could be viewed as "empirical evidence" to support $NP\neq PH$. After all, if $NP=PH$, then the two statements ($PH=PSPACE$ and $NP=PSPACE$) must have the same consequences. As the second hypothesis has noticeably more and stronger known consequences, that can be viewed as empirical evidence to support that the left-hand sides in the equations must be different, that is $NP\neq PH$ (which, in turn, is equivalent to $NP\neq coNP$).