# Using time hierarchy theorem to show $Time(n^7)$ strictly contained in P

I'm relatively new to computational complexity and am trying to use the time hierarchy theorem to show that $$Time(n^7)$$ is strictly contained in P. I understand that the time hierarchy theorem says that if the limit as n tends to infinity of $$\frac{T_1(n)}{T_2(n)}=0$$ then $$Time(T_1(n))$$ is strictly contained in $$Time(T_2(n))^2$$. It seems obvious to me that this implies the desired result because for any number $$x$$ greater than 7, $$Time(n^7)$$ will be strictly contained in $$Time(n^{2x})$$ and then P is the union over all such time complexity classes. Could anyone help with how I might write this more formally? Is it necessary to assume the existence of some language in $$Time(n^{16})$$ for example? I feel like I might be missing something because it just seems clear to me, any help is much appreciated.

• Why do you want to use the time hierarchy theorem? $\mathsf{DTIME}(n^7) \subseteq \bigcup_{k=0}^\infty \mathsf{DTIME}(n^k) = \mathsf{P}$. Commented Jan 9 at 11:04
• @Steven He wants to show $DTIME(n^7) \subsetneq P$ (stricly contained) Commented Jan 9 at 11:55
• "Is it necessary to assume the existence of some language" Not only you just assume it, time hierarchy theorem implies there is a language in $Time(n^{16})$ that is not in $Time(n^7)$. Commented Jan 9 at 13:01
• @jt0202. Thanks, I had missed that. Commented Jan 9 at 13:56

By the time hierarchy theorem, if $$f$$ and $$g$$ are time-constructible functions and $$f(n) \log f(n) = o(g(n))$$ then $$\mathsf{DTIME}( f(n) ) \subsetneq \mathsf{DTIME}(g(n))$$.
From your question you seem to be using the following weaker for of the theorem: if $$f$$ and $$h$$ are time-constructible and $$f(n) = o(h(n))$$ then $$\mathsf{DTIME}( f(n) ) \subsetneq \mathsf{DTIME}( h(n)^2 )$$. This follows from the previous statement by choosing $$g(n)=h(n)^2$$ and noticing that $$f(n) \log f(n) = O(f(n)^2) = o(h(n)^2)$$. I will therefore use this latter version.
Choosing $$f(n) = n^7$$ and $$h(n) = n^8$$: $$\mathsf{DTIME}( n^7 ) \subsetneq \mathsf{DTIME}( n^{16} ) \subseteq \bigcup_{k \in \mathbb{N}} \mathsf{DTIME}(n^k)=\mathsf{P}.$$