ZuoTi.Pro
Question

* SUBSET-SUM-kS, t> I S -[xi Xk] and for some lyı yn)cIxi.... xk) the sum of the yis 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 A-12, 3, 7) and A-14, 8} since 2+3+7= 4+8 a) Prove that SUBSET-SUM is in NP. b) Prove that SET-PARTITION is in NP I claim that SET-PARTITION is NP-complete and so if it reduces to SUBSET-SUM then SUBSET-SUM is NP-complete too. So I need to show that SET-PARTITION Sp SUBSET SUM. Mv reduction function is FOn input <S>(xi Xk) 1. Add up x Xk and to get y 2. If y is even then t - y/2 otherwise t- 0 3. Output <S, t> c) Either give a counter example or use the definition for sp to explain why my reduction function F either does or does not work d) Prove my claim that, if SET-PARTITION is NP-complete and if it reduces to SUBSET- SUM then SUBSET-SUM is NP-complete.

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Polynomial Sized The subset-sum problem is a set S of indices i from the set [nl, which correspond to the Ais which sum up to the number T. So the solution size could be at most n. So, it is polynomial in the input size. Polynomial time verification: Once we have the set S, we can verify the solution by summing up the corresponding Als and comparing this sum with T. The number of additions is at most n-1. So, the addition and comparison can be done in polynomial time. Hence, SUBSET-SUM is in NP Proof to prove that SET-PARTITION is in NP: To show that any problem A is NP-Complete, we need to show four things: 1, 2. 3. 4. there is a non-deterministic polynomial-time algorithm that solves A, ie, A E NP, any NP-Complete problem B can be reduced to A, the reduction of B to A works in polynomial time, the original problem A has a solution if and only if B has a solution. We now show that SET-PARTITION is NP-Complete. SET-PARTITION E E NP: Gums the two partitions and verify that the two have equal sums. Reduction of SUBSET-SUM to SET-PARTITION Recall SUBSET-SUM is de fined as follows: Given a set X of integers and a target number t, find a subset Y g X such that the members of Y add up to exactly t. Let s be the stun of members of X. Feed X XU(S- 2t) into SET-PARTITION. Accept if and only if SET-PARTITION accepts This reduction clearly works in polynomial time. we will prove that (X, t) SUBSET-SUM if and only if (X) E SET-PARTITION. Note that the sum of members of X is 2s-2t. 1. 2. 3. 4,

0 0
Add a comment
Know the answer?
Add Answer to:
* SUBSET-SUM-kS, t> I S -[xi Xk] and for some lyı yn)cIxi.... xk) the sum of...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

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

  • 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.

  • Given a set S of integers, we say that S can be partitioned if it can...

    Given a set S of integers, we say that S can be partitioned if it can be split into two sets U and V so that considering all u  U and all v  V, u = v. Let PARTITION = { <S> | S can be partitioned }. a. (5) Show that PARTITION  NP by writing either a verifier or an NDTM. b. (15) Show that PARTITION is NP-complete by reduction from SUBSET-SUM. 9.(20) Given a set...

  • Given a set S of integers, we say that S can be partitioned if it can...

    Given a set S of integers, we say that S can be partitioned if it can be split into two sets U and V so that considering all u  U and all v  V, u = v. Let PARTITION = { | S can be partitioned }. a. (5) Show that PARTITION  NP by writing either a verifier or an NDTM. b. (15) Show that PARTITION is NP-complete by reduction from SUBSET-SUM.

  • Given a set S of integers, we say that S can be partitioned if it can...

    Given a set S of integers, we say that S can be partitioned if it can be split into two sets U and V so that considering all u ∈ U and all v ∈ V, Σu = Σ v. Let PARTITION = { <S>| S can be partitioned }. a. (5) Show that PARTITION ∈ NP by writing either a verifier or an NDTM b. (15) Show that PARTITION is NP-complete by reduction from SUBSET-SUM.

  • 9. (20) Given a set of integers, we say that can be partitioned if it can...

    9. (20) 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 }. a. (5) Show that PARTITION € NP by writing either a verifier or an NDTM. b. (15) Show that PARTITION is NP-complete by reduction from SUBSET-SUM.

  • Given a set S of integers, we say that S can be partitioned if it can...

    Given a set S of integers, we say that S can be partitioned if it can be split into two sets U and V so that considering all u Î U and all v Î V, Su = Sv. Let PARTITION = { | S can be partitioned }. Show that PARTITION is NP-complete by reduction from SUBSET-SUM

  • 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...

  • 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...

  • 3. Let Xi, , Xn be i.i.d. Lognormal(μ, σ2) (a) Suppose σ-1, prove that S-X(n)/X(i) is an ancillar...

    3. Let Xi, , Xn be i.i.d. Lognormal(μ, σ2) (a) Suppose σ-1, prove that S-X(n)/X(i) is an ancillary statistics. (b) Suppose p 0, prove T-X(n) is a sufficient and complete statistics (c) Find a minimal sufficient statistics. 3. Let Xi, , Xn be i.i.d. Lognormal(μ, σ2) (a) Suppose σ-1, prove that S-X(n)/X(i) is an ancillary statistics. (b) Suppose p 0, prove T-X(n) is a sufficient and complete statistics (c) Find a minimal sufficient statistics.

  • Java 8 9m left Jav 27 28 ALL 29 0 Given an integer array, separate the...

    Java 8 9m left Jav 27 28 ALL 29 0 Given an integer array, separate the values of the array into two subsets, A and B, whose intersection is null and where the addition of the two subsets equals the entire array. The sum of values in set A must be strictly greater than the sum of values in set B, and the number of elements in set A must be minimal. Return the values in set A in increasing...

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