3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ That are bad news. I have here some problem, that is surely not in FNP, but I think I have an algorithms on polynomial space to solve it :( Nonetheless, thank you. $\endgroup$ – gubel Feb 25 '15 at 22:22
  • $\begingroup$ The inclusion is trivially not strict, since FPSPACE can give exponentially long outputs and FNP can't. $\hspace{.28 in}$ $\endgroup$ – user12859 Feb 25 '15 at 23:16
  • $\begingroup$ You mean: trivally strict, right? That is a glimmer of hope. unfortunately my algorithm does not produce exponentionial output. $\endgroup$ – gubel Feb 25 '15 at 23:51
  • $\begingroup$ @gubel : $\:$ Agh, yes I did mean trivially strict. $\;\;\;\;$ $\endgroup$ – user12859 Feb 26 '15 at 4:21
  • $\begingroup$ @RickyDermer I don't know what I was thinking. I edited my answer to reflect this. $\endgroup$ – Tom van der Zanden Feb 26 '15 at 8:36

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.