NP-completeness of a Generalized Version of Subset Sum

Question

I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem:

In subset sum, we are given a number $t$ and a collection $S$ of integers with $|S|=n$, and ask if we can use a subset $S'\subseteq S$ to sum up to $t$. We can generalize the problem by extending the operation allowed: instead with only addition, we can permit addition together with multiplication and parenthesization.

It seems with the extended case, the usual reduction technique of encoding 3SAT in the problem breaks down, as parenthesization together with multiplication is difficult to handle (on the other hand, it seems like multiplication itself is easier to handle, as it can be expressed as a summation of identical elements).

Intuitively this generalized problem looks much harder; however, I haven't managed to find a way to prove its NP-completeness. I'm wondering if it can be indeed proven to be NP-complete, and what sort of reduction technique could be used in this problem.

Answer 1

Without loss of generality consider an instance $\langle S, t \rangle$ of subset sum where $S$ contains only positive integers and $t \ge 1$ (zeros can be dropped from $S$, and the case $t=0$ is trivial).

Now build a new instance $\langle T, t' \rangle$ of your generalized version of subset sum by choosing $T = \{ (t+1)x : x \in S \}$ and $t'=t(t+1)$.

If the elements of a subset $S' \subseteq S$ sum to $t$, then the elements of $\{ (t+1)x : x \in S' \} \subseteq T$ sum to $\sum_{x \in S'} (t+1)x = (t+1)\sum_{x \in S'} x =(t+1)t = t'$.

If there is a subset $T' \subseteq T$ of elements that can be arranged in an expression $E$ (that uses only addition, multiplication, and parentheses) that evaluates to $t'$, then $E$ uses no multiplication. Indeed, if $E$ used at least one multiplication, it would evaluate to at least $(t+1)^2 > (t+1)t = t'$ since each of the involved factors must be at least $(t+1)$. As a consequence it must be that $t' = t(t+1) = \sum_{x \in T'} x$. Let $S' = \{ \frac{x}{t+1} : x \in T' \} \subseteq S$. We have that $\sum_{x \in S'} x = \sum_{x \in T'} \frac{x}{t+1} = \frac{1}{t+1} \sum_{x \in T'} x = \frac{t'}{t+1} = t.$

This shows that your version of generalized subset sum is NP-complete (membership in NP is trivial).

Answer 2

(Steven's solution works, but since I've already written mine, let it be here)

The standard reduction (e.g. as described here) almost works. All you have to do is to prohibit multiplication.

• For each number, you add a new highest-order digit, which is equal to $1$. Now, if we multiply these numbers, then we will immediately get more than the required sum.
• For each clause, we create $2$ numbers of form $1000...000$: they play the role similar to $x_i$ and $y_i$ (numbers for the clauses) in the slides: if we didn't select $x_i$ or $y_i$, we can select one of these numbers. This way, we can always make the highest-order digit to be what we want.
• The sum itself also gets a new highest-order digit, which is equal to $n + 2m$.