It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the Subset-Sum problem?
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
In general, each $NP$-hard problem can be reduced to all other known $NP$-hard problems (there exist hundreds).
For the subset-sum there is for a example knapsack. Subsetsum is a specialisation of knapsack.
The other way, if you could solve subset-sum in poly-time, then you would also be able to solve PARTITION (and 3-PARTITION and 4-PARTITION)
