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

1 Answer

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

• It might also be that the sum is not NP-hard. Jan 25 at 15:15
• @kutschkem: If you can make a nontrivial example I'd like to see it. Jan 25 at 16:27
• @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+. Jan 25 at 19:02
• @Spitemaster Thanks, yes that's the kind of problems I had in mind. Jan 26 at 7:11