0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.