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

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.

• This is a very odd question. We know that $DTIME(2^{\sqrt{n}})\neq DTIME(2^n)$, from the time hierarchy theorem. So you're basically asking to prove that $NP\neq DTIME(2^{\sqrt{n}})$? – Shaull Jan 1 '20 at 19:58
• @Shaull Yes indeed, I was thinking about contradicting the time hierarchy theorem and reach a conclusion that my initial assumption was wrong, hence $NP \neq DTIME(2^{\sqrt{n}})$, I tried proving it by constructing a langue in NP but not in the other one, or the opposite, but I couldn't come up with anything. – user574362 Jan 1 '20 at 20:33
• Try padding only $|x|^2$ 1's. – xskxzr Jan 2 '20 at 3:02
• @xskxzr How will this help me, can you explain your intuition? – user574362 Jan 2 '20 at 6:53

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}$$.