I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use Time Hierarchy.
I need to show that the following are either equal, on inclusive of one another...
TIME($2^{n^2}$) and TIME($n^3 \times 2^n$)
My intuition tells me that...
TIME($n^3 \times 2^n$) $\subset$ TIME($2^{n^2}$)
Can someone explain how I can prove this using the rules of Time Hierarchy?
Let: $$L := \lim_{n \to \infty} \frac{n^{3} 2^{n}}{2^{n^{2}}}$$
So: $$\text{log}_{2}(L) = \lim_{n \to \infty} \biggr( 3\log_{2}(n) + n - n^{2} \biggr) = -\infty$$
So $L = 2^{-\infty} = 0$. Thus: $\text{TIME}(n^{3}2^{n}) \subset TIME(2^{n^{2}})$.
Now the Time Hierarchy Theorem tells us that for time-constructible $f(n)$ (that is, $f(n) \geq n$), then $\text{TIME}(f(n)) \subsetneq \text{TIME}((f(n))^2)$.
Let $f(n) = n^{3}2^{n}$. So $(f(n))^{2} = n^{6}2^{2n} \in o(2^{n^{2}})$. Thus, $\text{TIME}(n^{3}2^{n}) \neq TIME(2^{n^{2}})$.