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.

Improve this question
$\endgroup$
2
  • 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$ Commented Aug 30, 2020 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$ Commented Aug 30, 2020 at 17:15

2 Answers 2

Reset to default
2
$\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).

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$.
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.