3 ms·
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.
by thatguysaguy 1y ago
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.
- dragontamer 1y agoThe article is about a new proof wherein P == PSPACE. Something we all intuitively expected but someone finally figured out an obscure way to prove it. -------- This is a really roundabout article that takes a meandering path to a total bombshell in the field of complexity theory. Sorry for spoiling but uhhh, you'd expect an article about P == PSPACE would get to the point faster....
- LPisGood 1y agoThis article is not about a proof that P = PSPACE. That would be way bigger news since it also directly implies P = NP.
- LPisGood 1y agoI think that since many people find it intuitive that P != NP, and PSPACE sits way on top of polynomial hierarchy that it is intuitive even if it’s unproven.
- porphyra 1y agoThere's not even a proof that P != EXPTIME haha EDIT: I am a dumbass and misremembered.
- doc_manhat 1y agoI think there is right? It's been a long time but I seem to remember it following from the time hierarchy theorem
- LPisGood 1y agoI thought there was some simple proof of this, but all I can think of is time hierarchy theorem.