Hardness of maximizing difference of functions Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it possible to characterize $g$ in relation to $f$ in a way that can be assured that maximizing $f-g$ is also NP-HARD?
I suspect there's not likely to be any characterization that is very useful.  The optimization problems can be hard or easy depending on $g$.
To give an analogy: you could ask for a characterization of functions $f$ for which it is NP-hard to maximize $f$.  Well, you're probably not going to find a useful one.