Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.

  • $\begingroup$ Notice that, for every $c$, $n^{\log n} > n^c$ eventually. (Actually, this happens exactly when $\log n > c$.) $n^{\log n}$ grows faster than any polynomial. $\endgroup$
    – usul
    Apr 23 '14 at 1:28

It is definitely more plausible, for the simple reason that $NP \subseteq TIME[O(n^{\log n})]$ is implied by $NP \subseteq P$. However, it is conjectured that $NP$ requires exponential time (this is known as the Exponential Time Hypothesis), and so both statements are conjectured to be false.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.