14
$\begingroup$

Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing

$$\sum_{x}g(x)=\sum_{x}f(x)+\sum_{x}h(x)$$

now if we know that $\sum_{x}f(x)$ and $\sum_{x}h(x)$ are two NP-Hard problems, what can we say about the hardness of $\sum_{x}g(x)$?

$\endgroup$
38
$\begingroup$

Nothing.

Lower bound: Suppose $h(x) = -f(x)$. Then $\sum_x g(x) = 0$, which is trivial to compute. If $\sum_x f(x)$ is NP-hard to compute, then $\sum_x h(x)$ will be too, but $\sum_x g(x)$ will be easy to compute.

Upper bound: Suppose $h(x) = f(x)$. Then $\sum_x g(x) = 2 \sum_x f(x)$, which is as hard as computing $\sum_x f(x)$, which is assumed to be NP-hard. Since NP-hard means (roughly speaking) NP-complete or harder, there is no upper bound on the complexity; it could be arbitrarily hard to compute $\sum_x g(x)$.

$\endgroup$
4
  • $\begingroup$ It might also be that the sum is not NP-hard. $\endgroup$
    – kutschkem
    Jan 25 at 15:15
  • 2
    $\begingroup$ @kutschkem: If you can make a nontrivial example I'd like to see it. $\endgroup$
    – Joshua
    Jan 25 at 16:27
  • 10
    $\begingroup$ @Joshua Graph theory is likely full of them - computing the number of graphs with n vertices and a certain property, then computing the number of graphs with n vertices without a certain property. Computing the number of graphs with n vertices is comparatively easy. If that's not non-trivial enough for you, I'm pretty sure computing which graphs have which chromatic number is NP-hard when the chromatic number is >3, but not for <3. So you could do f=>3, h=>4+, and g=>3+. $\endgroup$ Jan 25 at 19:02
  • $\begingroup$ @Spitemaster Thanks, yes that's the kind of problems I had in mind. $\endgroup$
    – kutschkem
    Jan 26 at 7:11

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.