Suppose, towards a contradiction, that $\rm{NTIME}(n)=\rm{P}$. Let $L\in\rm{NTIME}(n^{2})$ and let a NDTM $M$ that decides $L$ in $cn^2$ time, for some constant $c$. Consider now the language \begin{equation*} L_{\rm{pad}}=\left\{\langle x,1^{|x|^{2}}\rangle\colon x\in L\right\}. \end{equation*} $L_{\rm{pad}}\in\rm{NTIME}(n)$. To show this we construct the following NDTM $M'$: given an input $y$, check if there is a string $x$ such that $y=\langle x,1^{|x|^{2}}\rangle$. If there isn't some, output $0$. If yes, then simulate $M$ with input $x$ for $c|x|^{2}$ steps and output its answer.
Obviously, $M'$ decides $L_{\rm{pad}}$ and $M'$ runs in linear time. Indeed, for an input $y$, $M'$ will simulate $M$ for at most $c|y|$ steps since if $y=\langle x,1^{|x|^{2}}\rangle$ then $|y|=|x|+|x|^{2}$ and so $c|x|^2\leq c|y|$.
Thus, we have proved that $L_{\rm{pad}}\in\rm{NTIME}(n)=\rm{P}$. Now, clearly the function $x\mapsto \langle x,1^{|x|^{2}}\rangle$ is a polynomial time reduction from $L$ to $L_{\rm{pad}}$ and since $L_{\rm{pad}}\in \rm{P}$ we have also that $L\in \rm{P}$. Hence, $\rm{NTIME}(n^{2})\subseteq \rm{P}=\rm{NTIME}(n)$, which is a contradiction since from the Nondeterministic Time Hierarchy Theorem we have that $\rm{NTIME}(n)\subsetneq \rm{NTIME}(n^2)$.
My questions are the following:
- Is the computation of the running time of $M'$ correct?
- Is the final argument correct? It seems correct to me!