1
$\begingroup$

This question already has an answer here:

There is a similar question that has been asked, but my question addresses particular detail of an answer.

I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description:

SUBSET-SUM is defined as follows: Given a set X of integers and a target number t, find a subset Y from X such that the members of Y add up to exactly t. Let s be the sum of members of X. Feed X' = X U {s - 2t} into SET-PARTITION. Accept if and only if SET-PARTITION accepts.

What does "X' = X U {s - 2t}" (union?) and "Feed X' = X U {s - 2t} into SET-PARTITION" mean? How does this prove that SUBSET-SUM can be reduced to SET-PARTITION?

$\endgroup$

marked as duplicate by Kyle Jones, D.W., David Richerby, Juho, Luke Mathieson Jul 21 '15 at 4:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Yup, that means union. $\endgroup$ – D.W. Jul 18 '15 at 5:17
2
$\begingroup$

What you are doing here is adding a new element to your original set 'X'. The value for this new element is (s - 2t). Hence, X' now contains one extra element as compared to X.

The SET-PARTITION would "accept" if the provided set can be partitioned into two subsets with equal sum. We were already able to pick out a subset 'Y', from the set X, the sum of whose elements was 't'. If we include the extra element (s-2t) in this subset Y, the sum of its elements would now become ( t + s - 2*t ) = (s-t). This is also the sum of the elements which are remaining in the set (X - Y). Hence, X' can be divided into two subsets each of whose sum is (s-t).

$\endgroup$
  • $\begingroup$ I am confused. By 'S' you mean 'Y' right? $\endgroup$ – James the Great Jul 18 '15 at 17:45
  • $\begingroup$ Yes, I meant Y, I have updated my comment. $\endgroup$ – Abhigyan Mehra Jul 19 '15 at 6:05
  • $\begingroup$ Thanks! Took me a while to understand your answer. Whoever discovered this reduction must be a genius! $\endgroup$ – James the Great Jul 20 '15 at 1:59

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