# What is the relation of complexity class $L^L$ to other complexity classes?

What is the relation of complexity class $L^L$ to other complexity classes?

(Here $L^L$ is the complexity class of decision problems solvable by a TM in logspace with an oracle for a language in logspace.)

• What did you try? Where did you get stuck? Did you try simulating a logspace TM with a logspace oracle on a machine without the oracle and seeing how much space you need? Aug 19, 2017 at 13:18
• Does the definition of a logspace TM require that: the length of the query string is also bounded by log n? Aug 19, 2017 at 19:34
• To avoid this issue, you can limit the space constraint to the work tape alone, and require the oracle tape to be write only. Aug 20, 2017 at 5:14

$L$ is self-low, i.e. $L^L=L$. The reason being that you can compute each oracle call yourself, using additional logarithmic space.
• I thought $\mathsf{L^L}$ would be a machine with $\log^2 n$ space. Why not? This means that $\mathsf{DLOGTIME^{DLOGTIME} \notin L^L}$. Aug 19, 2017 at 10:01
• First, $L^L$ is a class of languages, not a machine. Also, I can't parse the statement $DLOGTIME^{DLOGTIME}\notin L^L$, perhaps you want to talk about inclusion. If this is the case, this holds since $DLOGTIME^{DLOGTIME}=DLOGTIME\subseteq L$. I think you want to say something along the lines of "I think that your naive translation of a logarithmic space machine with access to a logspace oracle results in a $log^2 n$ space machine rather than logspace". This is not the case, since you can reuse the space for oracle calls. Aug 19, 2017 at 10:10
• So, $\mathsf{L}$ is self-low unlike $\mathsf{EXP}$ and bigger non-deterministic complexity classes? And I can't understand why $\mathsf{DLOGTIME^{DLOGTIME}=DLOGTIME}$, because former is a class of languages recognizable in $O(\log^2 n)$ time. Aug 19, 2017 at 10:47
• I'm not sure about this now, but the fact that the lefthand side is trivially contained in $\log^2 n$ time does not mean there isn't a better bound. When talking about sublinear time you need to be careful, because if you talk about the standard Turing machine model (no random access) then you get the class of languages decidable in constant time. Also note that the the queries are only of logarithmic length, so $O(\log\log n)$ time is enough to simulate each query (again you need to be careful and allow random access also on the work tape). In any case, this is still included in $L$. Aug 19, 2017 at 17:00
• And yes, $L$ is self-low unlike $EXP$. Aug 19, 2017 at 17:02