# Prove or disprove that DTIME(n^2)=NL

I need to prove or disprove $DTIME(n^2)=NL$. It kind of feel obvious that I need to disprove it, because if I have non-deterministic machine $M$ that uses $\log n$ space, then it meets at most $|Q| n\log n\ 2^{\log n}=|Q|\log n \ n^2 = \omega(n^2)$ ($Q$ denotes the number of states) different configurations, which bounds the running time, therefore intuitively it looks like I'll need more then $n^2$ to run $M$.
Can someone explain to me how would you approach to these types of problems? Because I always find my self resorting to "trial and error" with diagonalization and padding arguements.

• @Ariel Neither of the classes is closed under polytime reductions so that's not gonna work. – David Richerby Jun 10 '16 at 9:34
• "I always find my self resorting to "trial and error"" -- that's the only way I know how. With experience, your guesses become better, but that's about it. (Of course, there are a handful of standard attempts and maybe proof techniques specialized to problems of the kind at hand, but that's rarely any help outside of class.) – Raphael Jun 10 '16 at 10:42

Let's say that a class $\cal C$ is closed under "reverse quadratic padding" if for any language $L$, if $Q(L) = \{\langle |x|, 0^{|x|^2} \rangle : x \in L \}$ belongs to $\cal C$ then $L$ also belongs to $\cal C$.

The class $\mathsf{NL}$ is closed under reverse quadratic padding: if $Q(L) \in \mathsf{NL}$, then we can decide $L$ itself in $\mathsf{NL}$ by simulating the decider for $Q(L)$. For that we use our ability to count up to $n^2$ (here $n$ is the input length), noticing that $O(\log(n^2)) = O(\log n)$.

In contrast, the class $\mathsf{DTIME}(n^2)$ isn't closed under reverse quadratic padding. Indeed, use the time hierarchy theorem to find a language $L \in \mathsf{DTIME}(n^3) \setminus \mathsf{DTIME}(n^2)$. Then $Q(L) \in \mathsf{DTIME}(n^2)$, whereas $L \notin \mathsf{DTIME}(n^2)$.