0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ (I think the case where the $g$'s co-domain is "absorbent values only" (for subtraction, ±∞) special.) $\endgroup$
    – greybeard
    Sep 14 '20 at 10:58
  • $\begingroup$ @greybeard thank you for your comment. I am not sure I understand it, could you elaborate a little? $\endgroup$
    – Daniel
    Sep 14 '20 at 11:37
  • $\begingroup$ If $D$ contains some constant function, you're done. Same if $D$ is closed under multiplication by some positive constant different from $1$. $\endgroup$ Sep 14 '20 at 11:46
  • $\begingroup$ Note that if maximizing $f$ is hard, then so is maximizing $g = f - 1$. However, maximizing $f - g = 1$ is trivial. $\endgroup$ Sep 14 '20 at 14:10
  • $\begingroup$ @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? $\endgroup$
    – Daniel
    Sep 14 '20 at 14:23
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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)$ $\endgroup$
    – Daniel
    Sep 15 '20 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.