I am having an extremely tough time with this homework question, wondering if anyone could help me (for all you theory aficionados, this one's for you).

There is a language $L$ with the following property: There is a Turing machine that decides $L$ in time $O(n^{2013}/\log^{2012} n)$, but there is no Turing machine that decides $L$ in time $O(n^{2012.9})$. Is this statement TRUE or FALSE?

My notion/idea is to use this Corollary that stems from the Time Hierarchy Theorem: For any two real numbers $1 \le e_1 < e_2$, we have $\mathrm{TIME}(n^{e_1}) \subsetneq \mathrm{TIME}(n^{e_2})$. I think I am on the right track but I need some help with this proof.

  • 1
    $\begingroup$ OK, so you want to use the Time Hierarchy Theorem. Sounds like a good strategy. So where do you get stuck? How have you tried to use the Time Hierarchy Theorem? We expect people to show us what they've tried and where they got stuck in the question, and I think you should try to say more about what you tried and why you are finding it difficult to figure out how to apply the Time Hierarchy Theorem. $\endgroup$ – D.W. Dec 10 '13 at 6:09

The question is about upper bound (which is $O(n^{2013} / (\log n)^{2012})$) and lower bound (which is $O(n^{2012.9})$) – do they correspond to each other?

According to definitions of Big-O and Ω we have to find constants $c_1$, $c_2$, and $n_0$ such that for $n\geq n_0$ two following inequalities are true:

$$c_1 n^{2012.9} \leq T(n) \leq c_2 n^{2013} / (\log n)^{2012}.$$

If such constants exist, then the lower bound must be less than upper bound for sufficiently large $n$:

$$c_1 n^{2012.9} \leq c_2 n^{2013} / (\log n)^{2012}.$$

Let's simplify this a little:

$$c_1 (\log n)^{2012} \leq c_2 n^{0.1}.$$

Can we find $n_0$ such that this inequality is true when $n \geq n_0$? Yes, sure – the power function eventually wins over the logarithm function, so the answer is TRUE.


Hint: Find $e_1,e_2$ such that $\mathrm{TIME}(n^{2012.9}) \subseteq \mathrm{TIME}(n^{e_1})$ and $\mathrm{TIME}(n^{e_2}) \subseteq \mathrm{TIME}(n^{2013}/\log^{2012} n)$. (You also have to take care of the big O's.)

  • $\begingroup$ how do you find that, just by plugging and chugging numbers? I dont get it. $\endgroup$ – AyBayBay Dec 11 '13 at 0:28
  • $\begingroup$ Please disregard above question, after analyzing the fellows answer below and thinking about the problem I got the solution. Thanks for your help $\endgroup$ – AyBayBay Dec 11 '13 at 0:33

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.