Composition of PSPACE/LSPACE functions

Question

Let $f,g:\Sigma^*\rightarrow\Sigma^*$. $f$ is computable in polynomial space. $g$ is computable in logarithmic space.

Show that $f \circ g$ and $g \circ f$ are computable in polynomial space. Would it be true, if both $f$ and $g$ were computable in polynomial space?

-- This is a problem from an old exam. I don't really get why is this question nontrivial. After all, if both of these functions compute their output in polynomially bounded space, for every word from $\Sigma^*$, then why does it matter if $g$ takes output of $f$ as its input?

Answer 1

I think for this question to be non-trivial you have to count the output tape as write-only and its usage not counting as part of the total space used. Under these conditions, an algorithm who's work tape is polynomial bounded can write down an exponential sized answer on the tape. On the other hand, a logarithm bounded one, can only write down a polynomial bounded answer.

Thus for $g(f(x))$ we have $|f(x)| \leq 2^{n^k}$ and so $g(f(x))$ uses $O(log(2^{n^k})) = O(n^k)$ space. Similar for $f(g(x)$, but this won't hold for two polynomial space bounded functions since the first might give an output of exponential size.

Answer 2

The major question here is how the space complexity is defined. It is usually defined such that the measured complexity is of the "work tape" only; the input tape is "read only" and the output tape is "write only" (you can write a character to it and then the writing head moves right; you can't fix later what you wrote).

In this model, a polynomial-space bound for computation does not imply the output is of polynomial size; indeed, polynomial-space bound allows for exponential runtime, and so exponentially-large output.