how to show that non-decision problem is NP-hard?


So far I could find out that problems which are NP-hard do not have to be decision problems.   

But how to show a non-decision problem is NP-hard?


Is it possible to show problem L is NP-hard by showing that another NP-hard problem B is reducible to L?   

Does B have to be NP-hard or NP-complete and why is it like this?



NP-hardness of non-decision problems
A definition of NP-hard is: if the problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time. This definition works for function problems.


Example: Consider the optimization problem "find the length of the shortest path in an instance of the traveling salesman problem." This is an optimization problem, not a decision problem. It is NP-hard because, in particular, if we can solve it then we can use that solution to solve the decision version of TSP, which is NP-complete. And by definition of NP-complete, if we can solve decision-TSP in polynomial time then we can solve any problem in NP in polynomial time.


Usually the reductions used here are "Cook" reductions which work as follows: We assume we have an oracle for problem B, and show a polynomial-time algorithm (where an oracle call happens in one time step) for solving A. This reduces A to B.


