FNP ⊂ FPSPACE or FNP ⊆ FPSPACE?

It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?

It is indeed the case that $FNP\subseteq FPSPACE$. Recall that a function in $FNP$ is of the form


Given an input $x$ and a polynomial-time predicate $F(x,y)$, if there exists a $y$ satisfying $F(x,y)$ then output any such $y$, otherwise output 'no.'

source: Complexity Zoo

To see that every problem in $FNP$ is also in $FPSPACE$, note that we may enumerate over all possible $y$ (which can have at most polynomial length) and test whether the predicate holds for any of them. This all can be done in polynomial space, since $y$ is of polynomial size and computing the predicate is polynomial-time (and thus polynomial-space).

Whether the inclusion is strict depends on how you view an $FPSPACE$ machine. The most common definition is to have a polynomial "working" tape and an unbounded (write-only) output tape and in this case, $FNP\subsetneq FPSPACE$ because the output can be exponential. If you restrict the output to what is on the working tape (and thus the output is polynomially bounded), then the question is open (and depends on whether $NP=PSPACE$).

StackExchange Computer Science Q#39816, answer score: 5