The Number Partition problem asks, given a collection of non-negative integers S = {x,...,n} whether or...

 

Transcribed Image Text:

The Number Partition problem asks, given a collection of non-negative integers S = {x,...,n} whether or not the integers can be partitioned into two sets A and A= S-A - such that xEA X = ) TEA X. 1. (7 points) Show that Number Partition is in NP. 2. (18 points) Show that Number Partition is NP-Complete. Describe your reduction and prove its correctness. (Hint: Subset Sum problem is a NP-Complete problem. Recall that in the Subset Sum problem we are given a collection of non-negative integers Y {y, y2,..., Ym} and a target integer t, we want to see if it is possible find a subset ZC Y such that the sum of integers in Z equals to t x x = t. xEZ The Number Partition problem asks, given a collection of non-negative integers S = {x,...,n} whether or not the integers can be partitioned into two sets A and A= S-A - such that xEA X = ) TEA X. 1. (7 points) Show that Number Partition is in NP. 2. (18 points) Show that Number Partition is NP-Complete. Describe your reduction and prove its correctness. (Hint: Subset Sum problem is a NP-Complete problem. Recall that in the Subset Sum problem we are given a collection of non-negative integers Y {y, y2,..., Ym} and a target integer t, we want to see if it is possible find a subset ZC Y such that the sum of integers in Z equals to t x x = t. xEZ

Answer rating: 100% (QA)

To show that Number Partition is in NP we need to demonstrate that given a solution we can verify it in polynomial time The certificate for the Number Partition problem is a subset A of S such that th... View the full answer