1
$\begingroup$

Assuming (the unlikely scenario) that the Polynomial Hierarchy collapses to second level. Thus, $\Sigma_2^p=PSPACE$.

How significant this result would be (broad consensus) as compared to the other open problems in TCS (the most important two being $P$ vs $NP$ and $NP$ vs $coNP$).

Most of the sources rightly point to the above two problems being the most important but despite most of the classes in complexity hierarchy falling under $PSPACE$, I am somewhat surprised not much has been discussed about it.

Is it something that is at the Turing Award or Breakthrough Prize level?

$\endgroup$
0
1
$\begingroup$

Since $\Sigma^{P}_2 \subseteq PH \subseteq PSPACE$, then showing this will prove that $PH=PSPACE$, showing, for example, this important implication.

In addition, another immediate but important implication is that the polynomial hirarchy collapses to $\Sigma^P_2$ - which shows that there is no gain in "strength" by adding more alternations above only 3 alternations (using the definition of $\Sigma^P_k$ as an alternating turing machine).

As $IP=PSPACE$, this might lead for some more room of thought whether the same statement can be said about interactive protocols - can it be said there exists some $r$ such that all of IP is contained in Arthur-Merlin protocols with only $r$ rounds (basically, is IP collapsing to AM with $r$ rounds)?

Therefore, yes - it definitely would be considered a big breakthrough.

$\endgroup$

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.