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}$?

  • $\begingroup$ 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. $\endgroup$ – Laakeri Apr 27 '20 at 5:04
  • 1
    $\begingroup$ @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}$ $\endgroup$ – D.R Apr 27 '20 at 5:44
  • $\begingroup$ 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. $\endgroup$ – Laakeri Apr 27 '20 at 7:00
  • 1
    $\begingroup$ The first sentence in this post is not an accurate statement of the ETH. $\endgroup$ – D.W. Apr 27 '20 at 7:32
  • $\begingroup$ If there is a $2^{n^{o(1)}}$ algorithm, then the time hierarchy theorem would separate NP from EXP. $\endgroup$ – Yuval Filmus Apr 27 '20 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.