HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.