4
$\begingroup$

So, a paper showed up on arXiv: https://arxiv.org/abs/1609.09562

The above states in the abstract that it contains a proof that $NP = PSPACE$

Since $NP \subseteq PH \subseteq PSPACE$, that would mean that $PH$ collapses, right? Well, the paper makes no mention of this and this seems pretty significant because "if $\mathcal{P}$ were true then PH would collapse to the second level" comes up for quite many propositions $\mathcal{P}$. I am afraid that I am missing something here. Does this paper's result imply that that $PH$ collapses to the first level?

$\endgroup$
  • 2
    $\begingroup$ The authors are not experts on complexity, so might have missed that. Also, the paper is likely wrong (but should be given a fair chance). $\endgroup$ – Yuval Filmus Oct 10 '16 at 18:05
  • 4
    $\begingroup$ I don't really see what you're asking. Your question already includes a trivial (and obviously correct) proof that NP=PSPACE implies that the polynomial hierarchy collapses. So it's obvious that, if true, the paper implies the collapse of the PH. Since evaluating the correctness of the paper is beyond the scope of the site, no question remains. $\endgroup$ – David Richerby Oct 10 '16 at 21:05
  • 1
    $\begingroup$ Ah my question is just that. I found a trivial proof of a major consequence of this paper. I'm not well versed in these matters so it could be my misunderstanding of the definitions that is causing some actually nontrivial to seem trivial. My question might be phrased "is this really this trivial?". It not being mentioned made me question my conviction in the trivial nature of this "proof". $\endgroup$ – Jake Oct 10 '16 at 21:09
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because you pretend to be confused about a trivial problem as an excuse to implicitly ask whether a very ambitious paper has any chance of being correct. $\endgroup$ – Thomas Klimpel Oct 17 '16 at 9:51

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.