Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)

Question

I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time Hierarchy Theorem.

After the assumption, I want to prove that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$.

The first case $\mathsf{NP} \subset \mathsf{DTIME}(2^{n})$, is trivial.

For the second case, let $L \in \mathsf{DTIME}(2^{n})$ and $M$ be a deterministic TM that can decide it, let $$L_{\mathrm{pad}} = \left\{\left\langle x,1^{2^{\sqrt{|x|}}} \right\rangle : x \in L\right\}.$$ I am not sure how, using $L_{\mathrm{pad}}$, I can reach a conclusion that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$, I feel like I am missing something and that my method is not in the right direction, or it is lacking an extra detail.

Answer 1

It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L_\mathrm{pad}= \left\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has the form $\left\langle x,1^{|x|^2-|x|-1} \right\rangle$, then simulates $M$ on $x$. This new TM determines whether $y\in L_\mathrm{pad}$ in $O(2^{|x|})=O\left(2^{\sqrt{|y|}}\right)$ time, so we have $L_{\mathrm{pad}}\in \mathsf{DTIME}\left(2^{\sqrt{n}}\right)$, thus $L_{\mathrm{pad}}\in\mathsf{NP}$ by your assumption. This means there exists a non-deterministic TM $M'$ that decides $L_{\mathrm{pad}}$ in polynomial time. Hence, we can construct a new non-deterministic polynomial-time TM that decides $L$ by first padding a comma and $(|x|^2-|x|-1)$ 1's to the input then simulating $M'$, which means $L\in\mathsf{NP}$.