2
$\begingroup$

Given two positive integers $c_1$ and $c_2$ such that $c_1 < c_2$, it's easy to prove that $n^{c_1}$ is $\mathcal{O}(n^{c_2})$ while $n^{c_2}$ is not $\mathcal{O}(n^{c_1})$. In general, for any functions $f(n)$ and $g(n)$ it is possible to determine which one (or both) is true, $f \in \mathcal{O}(g)$ or $g \in \mathcal{O}(f)$ using only definition of big-O notation. Thus it is not hard to see that TIME($n^{c_1}) \subsetneq$ TIME($n^{c_2})$ without using the Time Hierarchy theorem.

So, what is the meaning of the Time Hierarchy theorem and how and where can I use it?

$\endgroup$
2
$\begingroup$

You miss the meaning of the Time Hierarchy theorem, or perhaps of the classes TIME($n^k$) that you show.

It is indeed obvious that $O(n^k) \subsetneq O(n^{k+1})$, for instance. It is also clear that the set of Turing machines that run in time $O(n^k)$ is a strict subset of those that run in $O(n^{k+1})$.

However, it is not immediately obvious that the set of problems that can be solved by TMs in time $O(n^k)$ (i.e., the class TIME($n^k$)) is a strict subset of TIME($n^{k+1})$. For this much stronger statement, you need the Time Hierarchy Theorem. That is, you need to argue that there exists some problem that can be solved in time $n^{k+1}$ but not in time $n^k$. (Of course, this is just a special case of applying the theorem to polynomial running times.)

$\endgroup$
  • $\begingroup$ Thanks for clarification. Now I understand, big-O is used for classifications functions and Turing machines, while TIME($.$) is a problem class. That was the key point. $\endgroup$ – B.K. Dec 9 '17 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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