3
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 ...
1
(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.
...
1
There is a reduction proof here, with a lot of context:
https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/22/Small22.pdf
In short, the reduction is:
Let the machine $M'$ be defined as follows:
$M'$ = On input $⟨N, z⟩$:
Run $N$ on $z$.
If $N$ halts on $z$, accept
We run on $⟨M', ⟨M, w⟩⟩$, and get that $⟨M, w⟩ \in HALT_{TM} \iff ⟨M', ⟨M, w⟩⟩...
Only top voted, non community-wiki answers of a minimum length are eligible
