4 ms·
I believe that P != NP. But suppose someone finds a way to provably solve SAT in O(n**1000000), thus proving P = NP. It's polynomial, but still unusable for re
by not2b 5y ago
I believe that P != NP. But suppose someone finds a way to provably solve SAT in O(n**1000000), thus proving P = NP. It's polynomial, but still unusable for real problems.
Edit: fixing damage to my post by Hacker News, making people think I don't understand O-notation.
- chrisseaton 5y agoO(n*1000000) is O(n) isn't it?
- TrainedMonkey 5y agoO(n*1000000) is linear, polynomial would be O(N^Y), where Y is the degree of polynomial.
- shoo 5y agoin the case where Y=1 you both agree.
- yifanl 5y agolinear time complexity problems are a subset of polynomial time complexity problems, if we're being pedantic.
- ineedasername 5y agoI think we can all agree that being pedantic is part of the foundation that makes HN be HN.
- inspector-g 5y agoTypo? Did you mean O(n^1000000) ?
- not2b 5y agoNo, I typed two '*' characters, and it appears that this site made one of them go away. I meant n to the millionth power.
- DrBenCarson 5y agoIf 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.
- dllthomas 5y ago> 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.
- throwaway81523 5y ago> 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 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.