# relation between ntime and dtime

Given DTIME($n^2$) contains NTIME($n^{100}$) show that P=NP.

I think it's supposed to be straightforward but I just can't see it.

Take $L$, a language in NP. $L$ has a Turing machine which runs in NTIME$(f(n))$. If $f(n)$ is $\Omega(n^{100})$ it's obvious, but what about $O(n^{100})$?

• Welcome to CS.SE! Do you have things backwards in the last sentence? The case where $f(n) = O(n^{100})$ seems like the easy one. – D.W. Dec 21 '16 at 22:22
• Very closely related question; duplicate? – Raphael Apr 21 '17 at 5:08

Hint: What is the time complexity of the fastest nondeterministic Turing machine that is a decider for $SAT$?