1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If 3SAT is reducible to subset sum without using multiplication and parenthesization, it is certainly reducible to a version of the problem that includes them. So I don't understand where the difficulty lies in proving the extended subset sum problem is NP-complete. $\endgroup$ – Kyle Jones Aug 30 at 1:28
  • $\begingroup$ @KyleJones I think you misunderstood the concept of a reduction --- The problem is nontrivial in that it isn't "obviously reducible." As shown in Steven's answer, you need to do extra work to encode a subset sum problem inside this problem --- an algorithm for solving my "generalized subset sum" might not work directly out of the box for subset sum. $\endgroup$ – BearAqua Aug 30 at 17:15
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

(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$.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.