Question

Problem 2. In the Subset-Sum problem the input consists of a set of positive integers X...

Problem 2. In the Subset-Sum problem the input consists of a set of positive integers X = {x1, . . . , xn}, and some integer k. The answer is YES if and only if there exists some subset of X that sums to k.

In the Bipartition problem the input consists of a set of positive integers Y = {y1, . . . , yn}.

The answer is YES if and only if there exists some subset of X that sums to (Pn i=1 xi)/2.

We saw in class that the Subset-Sum problem is NP-complete. Show that the Bipartition problem is also NP-complete.

Hint: Devise a polynomial reduction from Subset-Sum to Bipartition. In your reduction you start with an input X, k of Subset-Sum and you construct an input Y of Bipartition. The goal is that there exists some subset of Y that sums to (P y∈Y y)/2 if and only if there exists some subset of X that sums to k. To that end, it might be a good idea to set Y to be equal to X, together with some additional integers that somehow encode k.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

It is easy to see that SET-PARTITION can be verified in polynomial time; given a partition P1,P2P1,P2just sum the two and verify that their sums equal each other, which is obviously a polynomial time verification (because summation is a polynomial operation and we are only performing at most |X||X| many summations).

The core of the proof is in reducing SUBSETSUM to PARTITION; to that end given set XX and a value tt (the subset sum query) we form a new set X′=X∪{s−2t}X′=X∪{s−2t} where s=∑x∈Xxs=∑x∈Xx. To see that this is a reduction:

  • (⟹⟹ ) assume there exists some S⊂XS⊂X such that t=∑x∈Sxt=∑x∈Sx then we would have that

    s−t=∑x∈S∪{s−2t}x,s−t=∑x∈S∪{s−2t}x,

    s−t=∑x∈X′∖(S∪{s−2t})xs−t=∑x∈X′∖(S∪{s−2t})x

    and we would have that S∪{s−2t}S∪{s−2t} and X′∖(S∪{s−2t})X′∖(S∪{s−2t}) form a partition of X′X′
  • (⟸⟸) Suppose that there is a partition P′1,P′2P1′,P2′ of X′X′ such that ∑x∈P′1x=∑x∈P′2x∑x∈P1′x=∑x∈P2′x. Notice that this induces a natural partition P1P1 and P2P2 of XX such that WLOG we have that

    s−2t+∑x∈P1x=∑x∈P2xs−2t+∑x∈P1x=∑x∈P2x

    ⟹s−2t+∑x∈P1x+∑x∈P1x=∑x∈P2x+∑x∈P1x=s⟹s−2t+∑x∈P1x+∑x∈P1x=∑x∈P2x+∑x∈P1x=s

    ⟹s−2t+2∑x∈P1x=s⟹s−2t+2∑x∈P1x=s

    ⟹∑x∈P1x=t⟹∑x∈P1x=t

Hence from a solution t=∑x∈Sxt=∑x∈Sx we can form a parition P1=S∪{s−2t}P1=S∪{s−2t}, P2=X′∖(S∪{s−2t})P2=X′∖(S∪{s−2t}) and conversely from a partition P′1,P′2P1′,P2′ we can form a soltuion t=∑x∈P′1∖{s−2t}xt=∑x∈P1′∖{s−2t}x and therefore the mapping f:(X,t)→X′f:(X,t)→X′ is a reduction (because (X,t)(X,t) is in the language/set SUBSETSUM ⇔X′=f(X,t)⇔X′=f(X,t) is in the language/set PARTITION) and it is clear to see that the transformation was done in polynomial time.

Add a comment
Know the answer?
Add Answer to:
Problem 2. In the Subset-Sum problem the input consists of a set of positive integers X...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • * SUBSET-SUM-kS, t> I S -[xi Xk] and for some lyı yn)cIxi.... xk) the sum of...

    * SUBSET-SUM-kS, t> I S -[xi Xk] and for some lyı yn)cIxi.... xk) the sum of the yi's equals t. For example, <S-2, 3, 5, 7, 11, 14], t-21> is in SUBSET-SUM because 3+7 11-21. xk) can be partitioned into two parts A and -A where -A * SET-PARTITION <S> S-Ixi S-A and the sum of the elements in A is equal to the sum of the elements in A. For example, 〈 S-12, 3, 4, 7, 8/> works because...

  • Show that PARTITION is NP-complete by reduction from SUBSET-SUM. Given a set of integers, we say...

    Show that PARTITION is NP-complete by reduction from SUBSET-SUM. Given a set of integers, we say that can be partitioned if it can be split into two sets U and V so that considering all u EU and all v € V, Eu = Ev. Let PARTITION = { <S> S can be partitioned ). Show that PARTITION IS NP-complete by reduction from SUBSET-SUM.

  • Subset Sum-2 Write an algorithm (in comments) and specify the big O, and a C program...

    Subset Sum-2 Write an algorithm (in comments) and specify the big O, and a C program to solve the problern below. Read the input for the set elements, the value of K from the user. Assume the size of the set is not bigger than 20. Subset Sum-3 Write an algorithm (in comments) and specify from the user. Assume the size of the set is not bigger than 20 1. Given a finite set of integers, is there a subset...

  • 5. The Hitting Set Problem (HS) is the following decision problem. Input. A finite set S,...

    5. The Hitting Set Problem (HS) is the following decision problem. Input. A finite set S, a collection (s1, s2,... , sn) of subsets of S, and a positive integer K. Question. Does there exist a subset t of S such that (a) t has exactly K members and (b) for i 1,..., n, sint6For example, suppose S # {1, 2, 3, 4, 5, 6, 7. the collection of subsets is (2.45), (34).(1,35) and K - 2. Then the answer...

  • Give a decision problem corresponding to each of the search problems given below. (a) • Input:...

    Give a decision problem corresponding to each of the search problems given below. (a) • Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the same period. • Output: The largest set of classes that can all be scheduled during the same period. Solution A • Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the...

  • Let X be a finite set and F a family of subsets of X such that...

    Let X be a finite set and F a family of subsets of X such that every element of X appears in at least one subset in F. We say that a subset C of F is a set cover for X if X =U SEC S (that is, the union of the sets in C is X). The cardinality of a set cover C is the number of elements in C. (Note that an element of C is a...

  • Please do problem 14.12 Problem 14.6. Let X be a nonempty set and let A be a subset of X. The character- istic function...

    Please do problem 14.12 Problem 14.6. Let X be a nonempty set and let A be a subset of X. The character- istic function or indicator function of the set A in X is 1 if x E A XA(x)-10 if xeX\A A-X→ {0,1} defined by Problem 14.12. See Problems 14.6, 14.7, and 14.11 for the definitions (a) Write the greatest integer function as a sum of characteristic functions (there may be more than one way to do this). Depending...

  • 2. In this problem, the domain of discourse is the set of positive integers: {1, 2,...

    2. In this problem, the domain of discourse is the set of positive integers: {1, 2, 3, ...}. Which statements are true? If an existential statement is true, give an example. If a universal statement is false, give a counterexample. (a) ∀x(x 2 − 1 > 0) (b) ∀x(x 2 − x > 0) (c) ∃x(x 3 = 8) (d) ∃x(x + 1 = 0)

  • Problem 3: (5 2 points) Design an algorithm that takes an array of positive integers A...

    Problem 3: (5 2 points) Design an algorithm that takes an array of positive integers A of length n and a positive integer T as an input and finds the largest N < T such that N can be written as a sum of some elements of A and returns such a representation of N. The complexity of the algorithms has to be O(nT). For example, for A 3,7, 10 and T 19, the output is 17 7+10, because we...

  • Consider the following four problems: Bin Packing: Given n items with positive integer sizes s1,s2,...,sn, a...

    Consider the following four problems: Bin Packing: Given n items with positive integer sizes s1,s2,...,sn, a capacity C for bins and a positive integer k, is it possible to pack the n items using at most k bins? Partition: Given a set S of n integers, is it possible to partition S into two subsets S1 and S2 so that the sum of the integers in S1 is equal to the sum of the integers in S2? Longest Path: Given...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT