Are these three subset sum problems hard? How to solve them?
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:
2. Instance: Given a set of $n$ integers ${a_1,\ldots,a_n}$, an integer $k\leqslant n$ and and integer $\sigma$.
3. 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$?
4. SSP2:
5. Instance: Given a set of $n$ integers ${a_1,\ldots,a_n}$, an integer $k\leqslant n$ and and integer $\sigma$.
6. 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$?
7. SSP3:
8. 603
Instance: Given a set of $n$ integers ${a_1,\ldots,a_n}$, an integer $k\leqslant n$ and and integer $\sigma$.
9. 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? 864