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.

  • $\begingroup$ PSPACE is a decision problem. So, shouldn't the output be only yes/no, and therefore have a constant size? $\endgroup$ – Tom Cornebize Jan 11 '17 at 21:22
  • $\begingroup$ @TomCornebize The question is about FPSPACE, which is a class of function problems. (Though I should maybe have said "FLOGSPACE", too. Having said that, everyone talks about "LOGSPACE reductions" rather than "FLOGSPACE".) $\endgroup$ – David Richerby Jan 11 '17 at 21:42
  • $\begingroup$ I think that's likely because FLOGSPACE sounds a bit too close to a ... ahem ... specialist members only club. $\endgroup$ – Luke Mathieson Jan 13 '17 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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