Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.