Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I can't comment on this question, so I ask it here as a new question:
Ricky Demer states there in a comment to the first answer
"[...] since FPSPACE can give exponentially long outputs [...]"
How can this be? How can an algorithm in FSPACE give an exponentially long output? Does this mean, that we do not count the output space in the definition of FSPACE (contrary to what I have believed so far)?
Space classes always only include working space: the model is that we have a read-only input tape and write-only output tape, plus a read-write work tape (or multiple such tapes) on which we're only allowed to use a bounded amount of space. This definition is necessary for something like LOGSPACE to make any sense: if you counted the output as part of the space used, then even an algorithm such as "just output the input" wouldn't run in LOGSPACE. That's important because we often want to use LOGSPACE reductions between problems.
A simple example of a (nontrivial) FPSPACE algorithm that produces exponentially much output is a SAT solver that just tries every possible combination of values for the variables and outputs the combinations that satisfy the formula. This will produce exponentially long output for the class of inputs $X_1\lor\dots\lor X_n$.
Note that, for TIME-bounded complexity classes, we don't have this kind of problem since, on a Turing machine, writing $\ell$ symbols of output always takes at least $\ell$ time steps so, e.g., a polynomial time machine can only produce polynomially much output.
