0
$\begingroup$

I do have some intuition(although I would like to be corrected) regarding why $NL!=Dtime(n^{log n})$ as for some $L \in Dtime(n^{log n})$ it might be required for the TM deciding it to read inputs of size $O(n^{log n})$ which isn't possible in logarithmic space constraints. Having an oracle access surely saves a lot of time, but how does it help with space constraints? We're still bounded by logarithmic space. Any help would be much appreciated!! Thanks!

$\endgroup$
0
$\begingroup$

The inclusion $\mathsf{NL\subseteq P}$ relativizes (remains true relatively to any oracle), from here you can apply the time hierarchy theorem.

$\endgroup$
1
  • $\begingroup$ Yaa, Time Hierarchy Theorem does prove containment in one direction as $Dtime(n^{c} )\subseteq Dtime(n^{log n})$, but I just want to confirm whether proving the reverse direction is possible at all i.e. $Dtime(N^{log n})^{O} \subseteq {NL}^O$ as for proving equality we need to show both the directions to be true. I don't think it's possible in the reverse direction for the same intuition as mentioned above. But as I am new to theory, I would like to validate my beliefs. $\endgroup$ Sep 15 at 2:11
0
$\begingroup$

First, see that we can prove two things as follows:

  • The Time hierarchy theorem relativizes. That is, one can prove that even with any oracle $O$, the following holds when $f(n) \log n = o(g(n))$: $$ DTime (f(n))^O \subsetneq DTime(g(n))^O $$
  • The proof that $$ NL \subseteq P $$ also relativizes. So: $$ NL^O \subseteq P^O $$ for any oracle $O$. The reason is that the TM for any language in $NL$, with oracle $O$, can be converted to a polynomial time, by the similar construction used for proof without oracle, and oracle query is replaced as it is.

Using these two one can just conclude that $NL^O \subsetneq DTime(n\log n)^O$

New contributor
TJTIARY is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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.