4 ms·
Is there a theorist who can put this into perspective? How excited should we be?
by sjackso 10y ago
Is 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.