# Does there exist a language O such that $NL^O= Dtime(n^{logn})^O$? How to proceed with the proof in either case?

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!

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

• 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. Sep 15 at 2:11

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.