Definition of NP-hardness for non-decision problems As I understand, the term &quot;NP-hardness&quot; is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-hardness for such problems? The standard definition:

The problem is NP-hard when any problem from NP is polynomial-time reducible to this problem

doesn't make much sense, because of how the reduction is defined:

Language $A$ is polynomial-time reducible to $B$ if there exists a poly-time computable function $f$, such that $x \in A$ iff $f(x) \in B$.

The problem is that $B$ (e.g. our search problem) doesn't define a language (there may be other equivalent definitions, such as $A(x) \in \{true, false\}$, but they'll lead to the same problems).
My friend suggested that we can define a second poly-time computable function $g^{-1}$, which converts an &quot;answer&quot; for $B$ to answer for $A$: $x \in A$ iff $g^{-1}(B(f(x)))$ is $true$, where $B(y)$ is any correct answer for $y$. This makes sense, but I've never seen that.
So, what's the standard definition? For an answer, I would also ask for an appropriate citation (not to Wikipedia or random slides).
There is a slight abuse of notation going on. We say that a function $f$ is NP-hard if $f\in FP$ implies $P=NP$. For example, if $L$ is NP complete and $M_L(x,y)$ is a verifier for $L$, then any function $f$ which maps $x$ to some $y$ such that $M_L(x,y)$ whenever such $y$ exists is of course NP-hard in this sense. We don't usually talk about actual reductions in this context, however the natural way to go about saying $L$ reduces to computing $f$ is to say that there exists a polynomial time oracle machine $M^f$ with access to $f$ that decides $L$.
See also the zoo on the class FNP. The fact that &quot;function NP&quot; problems are defined relative to a specific verifier introduces some difficulty when talking about search to decision reduction.