0
$\begingroup$

I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use Time Hierarchy.

I need to show that the following are either equal, on inclusive of one another...

TIME($2^{n^2}$) and TIME($n^3 \times 2^n$)

My intuition tells me that...

TIME($n^3 \times 2^n$) $\subset$ TIME($2^{n^2}$)

Can someone explain how I can prove this using the rules of Time Hierarchy?

$\endgroup$
0
$\begingroup$

Your intuition that $ \text{TIME}(n^3 \times 2^n) \subsetneq \text{TIME}(2^{n^2})$ is correct.

It is easy to see that $2^{n^2}$ is time-constructible. Given $n$, you can compute $n^2$ in $\log^2 n$ time, then write 100...00 with $n^2$ zeros, in time $O(n^2)$.

The Time-Hierarchy Theorem states that, for such time-constructible $f(n)$,

$$ \text{TIME}(o(\frac{f(n)}{\log f(n)})) \subsetneq \text{TIME}(f(n))$$

It is clear that $ n^3 \times 2^n \in o(\frac{2^{n^2}}{\log 2^{n^2}}) = o(\frac{2^{n^2}}{n^2}) $.

Therefore, $ \text{TIME}(n^3 \times 2^n) \subseteq \text{TIME}(o(\frac{2^{n^2}}{\log 2^{n^2}})) \subsetneq \text{TIME}(2^{n^2})$.

$\endgroup$

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.