Hacker News

points by thatoneengineer 3 days ago | 0 comments

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.