1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Steven
    Commented Jan 9 at 11:04
  • 1
    $\begingroup$ @Steven He wants to show $DTIME(n^7) \subsetneq P$ (stricly contained) $\endgroup$
    – jt0202
    Commented Jan 9 at 11:55
  • 1
    $\begingroup$ "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)$. $\endgroup$
    – rus9384
    Commented Jan 9 at 13:01
  • 1
    $\begingroup$ @jt0202. Thanks, I had missed that. $\endgroup$
    – Steven
    Commented Jan 9 at 13:56

1 Answer 1

1
$\begingroup$

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

$\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.