Definition of NP-hardness for non-decision problems

Question

As I understand, the term "NP-hardness" 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 "answer" 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).

Answer 1

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 "function NP" problems are defined relative to a specific verifier introduces some difficulty when talking about search to decision reduction.

Answer 2

You will not find a reference for "the standard definition" of NP-hardness. Some authors restrict the notion "NP-hard" to decision problems only, and use the definition of reduction you mention in your question (which is sometimes referred to as a "Karp reduction" or "many-one reduction"). Other authors use the term more loosely, and extend the notion to other types of problem (such as search or optimization problems). You can find a bit of historical background in Donald Knuth's "Postscript about NP-hard problems".

The wikipedia article explicitly discusses this (and gives some references):

A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H. [...]

Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H. [...] Awkwardly, it does not restrict the class NP-hard to decision problems, and it also includes search problems or optimization problems.

The suggestion of your friend has some similarities with Cook reductions, which are sometimes used as the more loose definition of "NP-hardness". The suggestion of your friend captures well what people usually mean when they talk about an optimization problem being NP-hard.