# Complexity of a sum with a product

Is the following problem NP-complete:

Input: A set of tuples $$T = \left\{ t_i=(a_i,b_i) | 1\le i\le n \right\}$$, an integer $$k$$ and numbers $$C,D\in \mathbb Q_{\ge 0}$$.

Question: Exists a subset $$S\subseteq T$$ with $$|S|\le k$$ and $$\sum_{t_i\in S} a_i - C\cdot \prod_{t_i \in S} b_i \ge D.$$

There are some related threads that did not really help me:

As the problem seems to be quite fundamental, I am quite sure that there exists a source. But I have not so many good ideas what that could be called like. I have found somewhat similar but not close enough problems:

However all relations to Knapsack result in the issue that in the presented problem there are no weights to the tuples/elements. And connections to subset-sum fail because I require $$\ge D$$.

The most desirable variant for me would be $$a_i\in \mathbb Q_{\ge 0}, b_i\in \mathbb Q\cap[0,1)$$, but I would also be happy with an idea for the case where $$a_i$$s and $$b_i$$s are integers.

• Let's assume $a_i\ge 0, b_i \in [0,1)$. WLOG, we can assume $|S|=k$. Consider these two extremes: (1) If each $b_i$ is close to 1, then the problem might be easy: $\prod b_i \approx 1 - \sum (1-b_i)$, so the problem becomes approximately $\sum (a_i+C-Cb_i) \ge D+1$, which can be solved with a greedy algorithm. (2) If each $b_i$ is far from 1, the problem also might be easy: $\prod b_i$ is exponentially small (in $k$), so the problem is approximately $\sum a_i \ge D$, which can also be solved with a greedy algorithm. Any ideas for how to handle intermediate cases?
– D.W.
Aug 29, 2022 at 17:32
• The idea is actually quite interesting. Indeed when the $b_i$s are relatively close to each other (informally) then we can approximate $$\prod_{t_i\in S} b_i \approx b_1^{|S|}.$$ And from that point we can go greedy about the $a_i$s. That generalizes the idea for "intermediate cases". So the the question is what about $b_i$s having quite values that are not so close to each other. Aug 30, 2022 at 9:31