Re:A proof P = NP was accidentally published in TOCT
by dllthomas on Tuesday July 20, 2021 @01:36AM
(#27890418)
> it’s only a matter of time until we have drastically better solutions than Y=1000000
Why? I'm likely missing something (and I'd love to know what!) but it seems plenty possible that some group of problems have a lower bound that's polynomial and still big.
Re:A proof P = NP was accidentally published in TOCT
by throwaway81523 on Tuesday July 20, 2021 @03:47AM
(#27891007)
> it seems plenty possible that some group of problems have a lower bound that's polynomial and still big.
Yes, that is a definite fact: https://en.wikipedia.org/wiki/Time_hierarchy_theorem
10000000 isn't that big a number anyway. We may be up against horrendous numbers that are so large that there is no concise way to write them down, even with recursive formulas such as Ackermann's function, or that sort of thing.
Everything in the digital world relies on P =/= NP. If that falls apart, we go back to the drawing board and start over.