# 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 think the case where the $g$'s co-domain is "absorbent values only" (for subtraction, ±∞) special.) Sep 14 '20 at 10:58
• @greybeard thank you for your comment. I am not sure I understand it, could you elaborate a little? Sep 14 '20 at 11:37
• If $D$ contains some constant function, you're done. Same if $D$ is closed under multiplication by some positive constant different from $1$. Sep 14 '20 at 11:46
• Note that if maximizing $f$ is hard, then so is maximizing $g = f - 1$. However, maximizing $f - g = 1$ is trivial. Sep 14 '20 at 14:10
• @Watercrystal yes, that is the point. With some engineered functions it is clear that $f$ can be hard but $f-g$ easy, being $f=g$ the simplest example. But which is in general the relation between the two functions for that to happen? Sep 14 '20 at 14:23

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.
• Thank you very much for your answer. It could very well be as you say. However, I feel that $f$ and $g$ must be in general connected somehow; if $f$ is hard and $f-g$ is easy, it seems that $g$ should have some specific structure that "removes complexity" from the problem, shouldn't it? For example, $g$ definition cannot allow the polynomial time computation of $max(f)$ from $max(f-g)$ Sep 15 '20 at 7:42