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.
replyThis 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.
replyThis 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.
replyNote https://news.ycombinator.com/item?id=50253213 which explains it better.
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.
replyDefinitely puts some weight on the P=NP side of the scale!
reply