3
$\begingroup$

Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$.

I read the proof that $L$ is closed under logspace reductions in Arora-Barak's textbook. The idea of the proof is, if I'm not getting wrong, to simulate the Turing Machine $M_B$ that computes the solution to $B$, carefully recomputing the $i$-th output bit of $f$ whenever we need it (so to save space).

My (probably naive) question is: since we are only interested in remaining within $L$, why can't we just compute the output of $f$ and store it entirely on the work tape of $M_B$ (this should require only logarithmic space), maybe separating it from the rest of the work tape with a special symbol, and use it as input to $M_B$? Since $B \in L$ this should require just an additional logarithmic amount of space, so there shouldn't be any risk to exit from $L$…where am I getting wrong?

$\endgroup$
4
$\begingroup$

The output of $f$ doesn't have to be of logarithmic size. This is why there is something to show.

To give an example, the function $f(x) = x$ can be computed in constant space but its output length is linear.

$\endgroup$
  • $\begingroup$ You're perfectly right, I was confusing the length of the output with the amount of space used in the work tape. Thanks! $\endgroup$ – Manlio Feb 3 '16 at 13:26

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.