Prove or disprove that DTIME(n^2)=NL - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-23T01:19:43Z https://cs.stackexchange.com/feeds/question/59497 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/59497 2 Prove or disprove that DTIME(n^2)=NL sel https://cs.stackexchange.com/users/44812 2016-06-10T09:14:48Z 2016-06-10T21:06:33Z <p>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$. <br/> 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.<br/> Thanks in advance.</p> https://cs.stackexchange.com/questions/59497/prove-or-disprove-that-dtimen2-nl/59518#59518 2 Answer by Yuval Filmus for Prove or disprove that DTIME(n^2)=NL Yuval Filmus https://cs.stackexchange.com/users/683 2016-06-10T21:06:33Z 2016-06-10T21:06:33Z <p>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$.</p> <p>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)$.</p> <p>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)$.</p>