2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – David Richerby Aug 19 '17 at 13:18
  • $\begingroup$ Does the definition of a logspace TM require that: the length of the query string is also bounded by log n? $\endgroup$ – user76270 Aug 19 '17 at 19:34
  • $\begingroup$ To avoid this issue, you can limit the space constraint to the work tape alone, and require the oracle tape to be write only. $\endgroup$ – Ariel Aug 20 '17 at 5:14
3
$\begingroup$

$L$ is self-low, i.e. $L^L=L$. The reason being that you can compute each oracle call yourself, using additional logarithmic space.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – rus9384 Aug 19 '17 at 10:01
  • $\begingroup$ 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. $\endgroup$ – Ariel Aug 19 '17 at 10:10
  • $\begingroup$ 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. $\endgroup$ – rus9384 Aug 19 '17 at 10:47
  • $\begingroup$ 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$. $\endgroup$ – Ariel Aug 19 '17 at 17:00
  • $\begingroup$ And yes, $L$ is self-low unlike $EXP$. $\endgroup$ – Ariel Aug 19 '17 at 17:02

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.