# How sub-exponential time does $\text{3SAT}$ have to be to make $\text{NP} \neq\text{EXP}$? What else would imply $\text{NP} \neq\text{EXP}$?

The exponential-time hypothesis posits that if $$\mathsf{3SAT}$$ has NO subexponential time algorithm (i.e. one in $$\mathcal O(2^{o(n)})$$), then $$\mathsf{P}\neq \mathsf{NP}$$. However, I am interested in the case that it does have such an algorithm.

From posts such as this, it seems that simply finding such an algorithm will not prove $$\mathsf{NP} \neq\mathsf{EXP}$$, so I am wondering just how subexponential the algorithm needs to be in order to guarantee this.

More generally, is there some sort of lists of conjectures/hypotheses that would imply $$\mathsf{NP} \neq\mathsf{EXP}$$?

• In order to prove that NP$\neq$EXP you would need to find a problem that is in EXP and not in NP, so investigating the complexity of SAT is not a correct approach because it is known to be in both. – Laakeri Apr 27 '20 at 5:04
• @Laakeri For example, if we know that 3SAT can be solved in $O(n^k)$ time for some k, then clearly $\text{NP}\neq \text{EXP}$. So I'm wondering if there is some intermediate level (between $2^{\log n}$ and $2^n$, say $O(2^{\sqrt n})$ s.t. knowing that 3SAT can be solved in this time implies $\text{NP}\neq \text{EXP}$ – D.R Apr 27 '20 at 5:44
• I see, this is by time hierarchy theorem, right? I guess for it to apply you need to have a complexity class that is closed under polynomial-time reductions. – Laakeri Apr 27 '20 at 7:00
• The first sentence in this post is not an accurate statement of the ETH. – D.W. Apr 27 '20 at 7:32
• If there is a $2^{n^{o(1)}}$ algorithm, then the time hierarchy theorem would separate NP from EXP. – Yuval Filmus Apr 27 '20 at 7:35