Question

Prove that $\mathbf{TIME}\mathbf{(}{\mathbf{2}}^n\mathbf{)}⊈\mathbf{TIME}\mathbf{(}{{\mathbf{2}}^2}^n\mathbf{)}$

Short answer

The above problem can be solved using Turing Machine, and the time hierarchy theorem which shows that the function $2n$is time constructible.

Step-by-step solution

Using the Time Hierarchy Theorem

The$\text{TIME}\left(2^n\right)\subseteq \text{TIME}\left({2^2}^n\right)$ holds because$2^n\le 2^{2n}$ .

According to the time Hierarchy theorem, if $f\left(n\right)\log f\left(n\right)=O\left(g\left(n\right)\right)$and f, g are time-constructible functions then,$D\text{TIME}\left(f\left(n\right)\right)⊈D\text{TIME}\left(g\left(n\right)\right)$

Thus, as discussed in time-hierarchy theorem the above containment

$\text{TIME}\left(2^n\right)\subseteq \text{TIME}\left({2^2}^n\right)$is proper

Using Turing Machine to prove the problem 

As we can write the number 1 followed by $2n$0s in$O\left(2^{2n}\right)$ time by making the function $2^{2n}$time constructible

Hence by the guarantees of the Time Hierarchy theorem, it can be decided whether a language A exists in $\mathbf{O}\mathbf{(}{\mathbf{2}}^{2n}\mathbf{)}$time but not in$\mathbf{o}\mathbf{(}\frac{{\mathbf{2}}^{2n}}{\mathbf{log}{\mathbf{2}}^{2n}}\mathbf{)}\mathbf{=}\mathbf{o}\mathbf{(}\frac{{\mathbf{2}}^{2n}}{2n}\mathbf{)}$

time.

So,$A\in \text{TIME}\left({2^2}^n\right)$but $A\notin \text{TIME}\left(2^n\right)$

Hence, we can say that.$\text{TIME}\left(2^n\right)⊈\text{TIME}\left({2^2}^n\right)$