Given a decision problem DEC which is PSPACE-Hard and a function problem FUN. If there is a polytime reduction from DEC to FUN, does this mean that FUN is FPSPACE-Hard?

In my case, the answer of the function problem is the one of the decision problem plus additional information. So it seems natural to assume that it is at least as hard. The question is whether this means that a lower bound for its complexity is the "function class" corresponding to the complexity class of the decision problem.


In the case of PSPACE and FPSPACE, the answer is yes (since DEC reduces to FUN and DEC is PSPACE-hard, FUN is FPSPACE-hard). The reason is that in PSPACE search always reduces to decision: say you want to compute a function $f(x)$. If the problem of deciding whether the $i$-th bit of $f(x)$ is 1, given $i$ and $x$, is in PSPACE, then $f$ itself is in FPSPACE. Now, if $f$ is in FPSPACE, we can use your function FUN to compute it by using FUN to compute the decision problem "is the $i$-th bit of $f(x)$ 1?" for each $i$. One way to say this is that PSPACE is FPSPACE-hard.

However, there are complexity classes where the relationship between the function and decision versions is not so clear. For example:

  • It is not known if the search version of Group Isomorphism (find an isomorphism) reduces to the decision version (is there an isomorphism?), when the groups are input as multiplication tables.

  • $P^{NP[\log]} = P^{NP}_{tt}$, but $FP^{NP[\log]} = FP^{NP}_{tt}$ is not known to hold and would imply $NP=RP$ and $P=UP$ (see Selman, A. A taxonomy of complexity classes of functions. JCSS 48(2):357-381, 1994.) But if $P^{NP}_{tt}$ were $FP^{NP}_{tt}$-hard, we would automatically have equality of the function classes.

(For reference: $P^{NP[\log]}$ is $P$ with an $NP$-oracle, but the $P$ machine is only allowed to make $O(\log n)$ queries to the oracle. $P^{NP}_{tt}$ is the problems that are polytime truth-table reducible to $NP$; this is equivalent to nonadaptive polytime Turing reductions, i.e. all the queries to be made are decided in advance, then all the queries are made, then some computation is done without queries to find the result.)

  • 3
    $\begingroup$ PPAD always comes to mind when looking at the relation between decision and search. $\endgroup$ Mar 25 '11 at 20:34
  • $\begingroup$ Are you assuming Turing reducibility in the first paragraph? It does not seem that every problem in FPSPACE is polynomial-time function (Levin) reducible to some decision problem in PSPACE. $\endgroup$ Mar 29 '11 at 1:15

Your Answer

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