logoalt Hacker News

lisper • yesterday at 11:03 PM • 7 replies • view on HN

This seems huge, like not quite p=np but in the same league. Am I missing something ?


Replies

krackers • yesterday at 11:07 PM

[deleted, originally wrote the hypothesis being true would imply NP=EXPTIME which is wrong, since there can be problems in EXPTIME which aren't in NP.

And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.]

➕ show 2 replies
lynndotpy • yesterday at 11:11 PM

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.

➕ show 1 reply
jaggederest • yesterday at 11:12 PM

This defeats a few hypotheses that were widely relied on.

strong exponential time hypothesis, and the titular exponential time hypothesis

It's not saying that these problems are easy, but it does demonstrate that they are much easier than previously believed. A decade ago if a human had published this kind of thing, and importantly if it held up, they would be almost certainly a strong candidate for some sort of award(s).

➕ show 1 reply
kakapo5672 • yesterday at 11:14 PM

My (very amateur) interpretation is that this weakens confidence in P!=NP. Would like to hear from some experts in this area, if this is so or not.

➕ show 4 replies
amelius • yesterday at 11:27 PM

Subexponential time still can mean much larger than polynomial time. There's a huge space between the two.

odyssey7 • yesterday at 11:08 PM

It’s not that it isn’t quite p=np; it actually isn’t p=np.

Still, an impressive accomplishment.

adgjlsfhk1 • yesterday at 11:06 PM

no. It's huge.