4 ms·
NP = PSPACE
- sjackso 10y agoIs there a theorist who can put this into perspective? How excited should we be?
- bertiewhykovich 10y agoI'm not a theorist, but PSPACE is a superset of NP (and therefore of P). This paper shows that there are no PSPACE problems that are not also NP problems -- intriguing, to be sure, but it doesn't seem to immediately speak to the relationship between P and NP.
- thealistra 10y agoYes it does, because there is a proof of P /= PSPACE. So the whole paper implies P /= NP
- chinhodado 10y agoI'm not a theorist, but I would not be excited. There's a paper coming out almost every month[1] claiming P=NP or P!=NP, for example. [1]: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm https://www.win.tue.nl/~gwoegi/P-versus-NP.htm
- throwawayaccnt3 10y agoI am also not a theorist. There are two questions to address; Will the result of this publication hold, and what is its significance? Testing this conclusion requires time and effort, in the measure of several years for serious examination if it gains traction. There are other publications on NP?=PSPACE, for which this process has had more time to advance, but the result is not widely accepted. NP=PSPACE is easily seen to be significant with the corollaries NP=co-NP and the collapse of the polynomial time hierarchy. These two conclusions are said to be considered unlikely by experts. Rather than excitement, this topic requires our patience and the diligence of the professionals.
- bertiewhykovich 10y agoThis is a far better answer than mine. I appreciate the emphasis on implications beyond P?=NP -- it's good to remember that there's unpopular work that's still tremendously important.
- deleted 10y ago[deleted]
- robinhouston 10y agoScott Aaronson said (in a comment on his blog), “suffice it to say my prior is so overwhelmingly against this standing as not to be particularly interested in spending time on it.” I'd be willing to bet a lot of money this isn't right. It's hard to convey how implausible it is that NP could equal PSPACE, and the proof strategy is just “Here is an NP algorithm for a PSPACE-complete problem”. They haven't attempted to implement the algorithm, as far as I can see. Presumably if this claim gets enough attention, someone will go to the trouble of working out where the mistake is in the proof.