logoalt Hacker News

lynndotpy • yesterday at 11:11 PM • 1 reply • view on HN

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.


Replies

cochne • yesterday at 11:26 PM

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

➕ show 2 replies