patternMinor
$NP\subseteq TIME[O(n^{\log n})]$
Viewed 0 times
subseteqtimelog
Problem
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.
Solution
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.
Context
StackExchange Computer Science Q#24033, answer score: 6
Revisions (0)
No revisions yet.