2
$\begingroup$

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}$.)

$\endgroup$

1 Answer 1

2
$\begingroup$

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>0$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.