Are these three subset sum problems hard? How to solve them?

Question

After asking this question I was thinking about some variants of subset sum problem (SSP).

The usual subset problem is the following.

• Instance: Given a set of $n$ integers and an integer $\sigma$.
• Question: Is there a non-empty subset that sums to $\sigma$?

The three variants of subset sum that I thought about are (I assume that all integers are positive):

1. SSP1:
   • Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
   • Question: Is there a non-empty subset of cardinality at most $k$ that sums to $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i=\sigma$ and $|S|\leqslant k$?
2. SSP2:
   • Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
   • Question: Is there a non-empty subset of cardinality at most $k$ that sums to at most $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\leqslant\sigma$ and $|S|\leqslant k$?
3. SSP3:
   • Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
   • Question: Is there a non-empty subset of cardinality at most $k$ that sums to at least $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\geqslant\sigma$ and and $|S|\leqslant k$?

My question is: Are these problems (SSP1, SSP2 and SSP3) hard?

My claim is the following: SSP1 is NP-complete but SSP2 and SSP3 are polynomial-time solvable.

My Proof (intuitive and incomplete):

• For SSP1, if I can find a subset $S$ of cardinality at most $k$, then $S\neq\emptyset$ and hence I have solved SSP.
• For SSP2, sort $\{a_1,\ldots,a_n\}$ in the ascending order. Select the first $k$ elements. If their sum is less than $\sigma$ then we are done. Else remove the biggest elements of the selected $k$ elements and see. Continue.
• For SSP3, sort $\{a_1,\ldots,a_n\}$ in the descending order. Select the first $k$ elements. If their sum is greater than $\sigma$ then we are done. Else output no.

Is my work correct?

Answer 1

Your work is mostly correct:

• SSP1 is clearly in NP. Moreover, it is NP-hard by reduction from SUBSET-SUM: given an instance of SUBSET-SUM, reduce it to the corresponding instance of SSP1 with $k = n$.

• SSP2: Let $m$ be the number of negative elements in $\{a_1,\ldots,a_n\}$, and let $S$ be the sum of the $\min(m,k)$ smallest of them. Check whether $S \leq \sigma$. This is a polynomial time algorithm.

• SSP3: Can be reduced to SSP2 by negating the set and $\sigma$. (We can also solve it directly just like SSP2.)