0
$\begingroup$

I read a commonly known proof of transitivity of logspace reduction: Lemma 6.: http://www.cs.au.dk/~arnsfelt/CT10/scribenotes/lecture5.pdf . In this proof it is used following trick: Let some turing machine $M_f$ for language $f$ compute only $j$-th bit of output. Ok, $M_f$ is logspace machine, however tape with output can require $O(n)$ space. Hence, we can't get $j$-th bit in such easy way.

Where am I wrong ?

$\endgroup$
0
$\begingroup$

$L_f$, by definition, gives you the output of $f(x)$ for a single bit $j$. Note that we do not have to copy $x$, so we're only storing $bin(j)$ and the $j$-th bit of $f(x)$, which is in logarithmic space. Since $M_f$ computes $L_f$ with logarithmic space, we can simply get the $j$-th bit. This means that $M_h$ can work in logspace in total, as it only asks and stores a single bit of input from $M_f$ every time.

$\endgroup$
6
  • $\begingroup$ I understand what do you mean, however I can't see how this proof works. After all, we shouldn't assume that machine $M_f$ returns chosen $j$-th bit of output. We should show a way which use standard machine $M_f$ which get input and return entire output. To my eye there must exists any way to modify machine for $f$ that it returns chosen bits of output instead of entire output. Hmm ? $\endgroup$
    – user54001
    Apr 30 '17 at 17:50
  • 1
    $\begingroup$ By definition, machine $M_f$ computes the language $L_f$ in log space. Since $x$ and $bin(j)$ are on the tape and the alphabet of our machine is finite, we can simply try all values of $y$ and see which one accepts. In this way, we can find the value of $f(x)_j$ using only $M_f$. $\endgroup$
    – Discrete lizard
    Apr 30 '17 at 19:04
  • $\begingroup$ Wait, wait. The general aim is to show that (logspace $\circ$ logspace)$\in$logspace. Now (when you highlight finitness of alphabet) I got how to check symbol $y$ in logspace. You are right, it uses defintion of $L_f$. However try to help me please understand how it shows closure of logspace on $\circ$. Here somebody introduce some defintion. However, in general case we can't introduce some special definition (which defeat main difficulty in this problem). So let's get logspace TM $K$ and $L_K$ - how to transform TM $K$ to analogous machine to $M_f$ in logspace? Thanks for your help. $\endgroup$
    – user54001
    Apr 30 '17 at 21:31
  • $\begingroup$ To be precisely - we have two Turing machines: $K$ and $X$. Both works in logspace and decides languages $L_K$ and $L_X$. We would like to compse ($\circ$) these two languages and prove that this composition is also decidable in logspace. However, in order to use this proof we should transform these machines to machines that get on input not one word, but $\langle x, bit(j), y\rangle$. Moreover, this transformation should be done in logspace. $\endgroup$
    – user54001
    Apr 30 '17 at 21:36
  • 1
    $\begingroup$ Well, uh, the document you referenced uses the definition of $L_f$ to define a reduction. Since the machines decide whether inputs of the form $\langle x, bit(j), y\rangle$ are in $L_f$ for $f=X,K$, the construction in the proof directely applies. You can't do a reduction without the definition of $L_f$ in this context. It is perfectly general, in the sense that for all reductions we have a logspace TM deciding $L_f$, by definition of reductions. If you want to remove that definition, you have to come up with a different way of defining reductions. $\endgroup$
    – Discrete lizard
    Apr 30 '17 at 21:43

Your Answer

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