Consequences of the Time Hierarchy Theorem The form of the Time Hierarchy Theorem that I have is this:


  If $f$ is time constructible then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(2n+1)^3)$.


We want the consequences of this to be that $\text{P} \neq \text{EXP}$ and $\text{EXP} \neq \text{2-EXP}$ etc. But I can't see how this follows.

I have $\text{P}$ defined as $\text{P} := \bigcup_{c=0}^\infty \text{DTIME}(n^c) $ and $\text{EXP}$ as $\text{EXP} := \bigcup_{c=0}^\infty \text{DTIME}(2^{n^c}) $.

I know that $\text{DTIME}(n^c) \subsetneq \text{DTIME}((2n+1)^c)=\text{DTIME}(2^c(n+0.5)^c)$. But $c$ is a constant, so surely the RHS is just another polynomial class.

Additionally, even if I had, say, $\text{DTIME}(n^c) \subsetneq \text{DTIME}(2^{n^c})$, how would I know that the limit of infinitely many of these classes still preserves the "not equal to" relation? (For instance, $\{n\} \subsetneq \{n, n+1\}$ but $\bigcup_n \{n\} = \bigcup_n \{n, n+1\} = \mathbb{N}$.)
Let $f(n) = n^{\log n}$. Then $\mathsf{P} \subseteq \mathsf{DTIME}(f(n))$ while $\mathsf{DTIME}(f(2n+1)^3) \subseteq \mathsf{EXP}$.

(Actually, whether this argument works depends on the exact definition of $\mathsf{DTIME}$. If it doesn't, take $f_C(n) = Cn^{\log n}$ and sum over all integer $C&gt;0$.)