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)$?

Improve this question
$\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)$.

Improve this answer
$\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$ – Spitemaster 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.