# Composition of PSPACE/LSPACE functions

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?

-
in your second paragraph you say "polynomially bound time", do you mean "polynomial bounded space"? –  Artem Kaznatcheev Aug 25 '11 at 12:12
@Artem: yes, fixed. –  zxc Aug 25 '11 at 12:14

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.