Hacker News

points by jaggederest 3 days ago | 0 comments

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

[–] thatoneengineer 3 days ago

Assuming P != NP (and that this NP != EXP proof holds up), what's the next most "natural" candidate for how fast NP must grow? This paper appears to show Omega(2^(n/sqrt(log(n))) with a couple additional fudge factors which would be a very disappointing answer.

[–] jibalt 3 days ago

This is not a proof that NP != EXP. 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.

[–] xigoi 2 days ago

Even if all NP problems could be solved in sub-exponential time, it would not imply that NP ≠ EXP. It seems that many people here are confused about what EXP means – it’s the set of all problems that can be solved in at most exponential time, including those in P.

[–] zeroonetwothree 3 days ago

Definitely puts some weight on the P=NP side of the scale!

[–] xigoi 2 days ago

This is not a proof of NP ≠ EXP. NP ≠ EXP would mean that there is a problem that can be solved in exponential time, but not in non-deterministic polynomial time. That’s completely different from what they have shown.

[–] SkiFire13 2 days ago

Not sure about how "natural" Omega(2^(n/sqrt(log(n))) is, but a huge intermediate result would be proving that QP = NP or QP != NP.