If I am understanding this correctly (and I am still reading this!) and if this is true, this means NP is sub-exponential. Sub-exponential does not mean P=NP. But yes, this is huge if true.
This means hard problems aren't as hard as we thought, and it's still possible P=NP. If it turns out to be true P=NP, we're a little closer to that. (I hope P!=NP!)
Every paper which assumes ETH is true might now have their conclusions be disproven.
It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.
No. NP is always poly time reduceable to 3SAT
See this from the paper: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems
admit subexponential time algorithms."
loading story #50252831
loading story #50252822
loading story #50253240
loading story #50253837
loading story #50254123
loading story #50252900
{"deleted":true,"id":50252679,"parent":50252623,"time":1793057536,"type":"comment"}