3 ms·
> P is big. You just won't believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think a cubic time algorithm is very slow, but that's just pea
by enriquto 5y ago
> P is big. You just won't believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think a cubic time algorithm is very slow, but that's just peanuts to P.
I hate that P is often understood as "easily solvable". There's problems inside P that require O(n^A) time algorithms, where A is some scaringly large ackerman number. And that just barely scratches the surface of P. There are other, unimaginably harder, problems in P.
It is very arrogant for us to say that P<NP, when we still know so little about P.
I'm rooting for P=NP, even if this only serves to explore harder problems inside P, with terrifyingly slow algorithms.
- baq 5y agoEasily solvable in the context of all other problems being harder ;)
- archibaldJ 5y agoAnd don’t get me started in PSPACE There are so much we don’t know about how space & time complexities commune The weird thing is that GPT3 Codex can perhaps be used to solve some (space-constrainted) subsets of problems that are combinatorial weird. Maybe by pouring all these training data to it it is approximating some unimaginable algo in P that we have no knowledge about Will be wild if there is some (time-space) correspondence; NPSPACE = PSPACE Implies NP = P would be interesting