Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$?
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)$.
