World's most popular travel blog for travel bloggers.

[Solved]: $NP\subseteq TIME[O(n^{\log n})]$

, , No Comments
Problem Detail: 

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.

Asked By : 0x41414141

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback