[Solved]: Are there problems with complexity between $O(n^c/\log^b n)$ and $O(n^{c - \varepsilon})$?

Problem Detail: 

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.

Asked By : AyBayBay

Answered By : HEKTO

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18810

3.2K people like this

 Download Related Notes/Documents