Re:A proof P = NP was accidentally published in TOCT
by DrBenCarson on Monday July 19, 2021 @11:39PM
(#27889824)
If SAT is solvable in polynomial time it’s only a matter of time until we have drastically better solutions than Y=1000000. Not only that, every commercial server in the world is optimized for long-running P-time implementations.
Everything in the digital world relies on P =/= NP. If that falls apart, we go back to the drawing board and start over.
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.
Re:A proof P = NP was accidentally published in TOCT
by TrainedMonkey on Monday July 19, 2021 @06:01PM
(#27887764)
O(n*1000000) is linear, polynomial would be O(N^Y), where Y is the degree of polynomial.
Re:A proof P = NP was accidentally published in TOCT
by yifanl on Monday July 19, 2021 @06:04PM
(#27887789)
linear time complexity problems are a subset of polynomial time complexity problems, if we're being pedantic.
Re:A proof P = NP was accidentally published in TOCT
by ineedasername on Monday July 19, 2021 @06:19PM
(#27887952)
I think we can all agree that being pedantic is part of the foundation that makes HN be HN.
Re:A proof P = NP was accidentally published in TOCT
by shoo on Monday July 19, 2021 @06:05PM
(#27887812)
in the case where Y=1 you both agree.
Re:A proof P = NP was accidentally published in TOCT
by chrisseaton on Monday July 19, 2021 @06:05PM
(#27887809)
O(n*1000000) is O(n) isn't it?
Re:A proof P = NP was accidentally published in TOCT
by hosteur on Monday July 19, 2021 @06:53PM
(#27888214)
Yes
Re:A proof P = NP was accidentally published in TOCT
by not2b on Monday July 19, 2021 @07:37PM
(#27888515)
Right, but apparently Hacker News changes a * followed by another * into one *, even though several languages use two asterisks as the exponentiation operator.
Re:A proof P = NP was accidentally published in TOCT
by inspector-g on Monday July 19, 2021 @07:13PM
(#27888335)
Typo? Did you mean O(n^1000000) ?
Edit: fixing damage to my post by Hacker News, making people think I don't understand O-notation.