3 ms·
To give a bit of context (context that wasn't obvious just from the abstract, at least to me): this paper makes progress on, amongst other things, P!=NP.
by eru 2y ago
To give a bit of context (context that wasn't obvious just from the abstract, at least to me): this paper makes progress on, amongst other things, P!=NP.
- LPisGood 2y agoIt makes more progress on P != PSPACE, which is a ridiculously big class containing the entire polynomial hierarchy (PH is essentially the union over all n of NP recursively relativized to itself n many times)
- eru 2y agoYes, I know. But I assumed that people would be more familiar with P vs NP. Specifically, we know that P <= NP <= PSPACE. And any progress on P < NP would automatically involve some progress on P < PSPACE. And while a proof of P < PSPACE by itself wouldn't strictly say anything about P vs NP directly, it would probably at least give some inspiration and hints.
- IsTom 2y agoI've always found it odd that people are fixating on showing P != NP when they can't even show that P != PSPACE.