2
$\begingroup$

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.
Thanks in advance.

$\endgroup$
  • $\begingroup$ @Ariel Neither of the classes is closed under polytime reductions so that's not gonna work. $\endgroup$ – David Richerby Jun 10 '16 at 9:34
  • 2
    $\begingroup$ "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.) $\endgroup$ – Raphael Jun 10 '16 at 10:42
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.