3 ms·
It 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 N
by LPisGood 2y ago
It 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.