# Complexity class when reducing decision problem to function problem

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