NP-completeness of a Generalized Version of Subset Sum 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.
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 &gt; (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).