Comment by lynndotpy

13 hours ago

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.

14 comments

lynndotpy

Reply
cochne  12 hours ago

It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.

  • lynndotpy  1 hour ago

    Yeah, I was wrong. Page two too, I commented too soon.

    NP is not yet proven to be subexponential but still, ETH disproven is huge

  • wbl  12 hours ago

    No. NP is always poly time reduceable to 3SAT

    • cochne  12 hours ago

      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."

      5 replies →

    • mswphd  11 hours ago

      practically, a poly-time reduction can increase teh size of hte problem instance. So maybe you transform a 3-color instance (graph on n vertices) into a n^2 sized SAT instance. You can then solve this in time 2^{n^2 / sqrt{log{n^2}}}, but this is not sub-exponential.

    • jibalt  10 hours ago

      Your "No" is wrong. As he said, "Conversions to other problems can still end up exponential", so (NP is poly time reduceable to 3SAT + 3SAT is sub-exponential) does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.

      Note https://news.ycombinator.com/item?id=50253213 which explains it better.