# Hardness of a problem which is the sum of two NP-Hard problems

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

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