HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

L closed under logspace reduction

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
underclosedlogspacereduction

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#52641, answer score: 4

Revisions (0)

No revisions yet.