Please type your solution very clearly
- Theory Of Computation Please Type Your Solution Very Clearly 1 (136.9 KiB) Viewed 92 times
Theory of Computation. Please type your solution very clearly
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Theory of Computation. Please type your solution very clearly
Theory of Computation.
Please type your solution very clearly
4. Consider the following language PARTITION = {s= (81, 82, - Sn) There is a subset RC S where [R=s\r} S .. a Rς s ΣR =ΣS\R} = = We are given a set of numbers. We want to determine if we can partition the set into two sets such that the two partitions add up to the same amount. For example 7 2 • (1, 1, 2, 4,6) E PARTITION because we can partition it into (1, 2, 4) and (1,6), both of which add up to the same number • (3,3,3,3,3) € PARTITION because no matter how you split it up there will be more 3s in one set than the other. (a) (5 points) Show that PARTITION E NP. (Hint: construct a machine that either guesses a partition or verifies that a given partition is valid) (b) (10 points) Show that PARTITION is NP-Hard. This, along with the original problem, will establish that PARTITION is NP-complete (Hint: reduce from SUBSET-SUM. Try introducing the number 2B – (si) into the original set of numbers.)
Please type your solution very clearly
4. Consider the following language PARTITION = {s= (81, 82, - Sn) There is a subset RC S where [R=s\r} S .. a Rς s ΣR =ΣS\R} = = We are given a set of numbers. We want to determine if we can partition the set into two sets such that the two partitions add up to the same amount. For example 7 2 • (1, 1, 2, 4,6) E PARTITION because we can partition it into (1, 2, 4) and (1,6), both of which add up to the same number • (3,3,3,3,3) € PARTITION because no matter how you split it up there will be more 3s in one set than the other. (a) (5 points) Show that PARTITION E NP. (Hint: construct a machine that either guesses a partition or verifies that a given partition is valid) (b) (10 points) Show that PARTITION is NP-Hard. This, along with the original problem, will establish that PARTITION is NP-complete (Hint: reduce from SUBSET-SUM. Try introducing the number 2B – (si) into the original set of numbers.)