Consider the following problems

In the PARTITION problem, we are given a finite set of integers S {a1, a2, . . . , an}. We are asked to determine if the set can be partitioned into two distinct subsets S1 and S2 (that is, Si US.-S and Si n S2 = 0) such that the sum of the items in each set is equal. .

In the TWO-MACHINE-SCHEDULING problem, we are given a finite set of integers S = {a1, a2, , an} and a bound D. We are asked to determine if the set can be partitioned into two distinct subsets S1 and S2 (that is, S1 US2 = S and Si n S2 such that the sum of the elements in each set is at most D (The intuition: the elements of S are jobs with specified run times, and D is the deadline for completing all of the jobs.

Is it possible to complete all of the jobs on two machines before the deadline?)

Assume that PARTITION is NP-complete. (It is, by the way.)

Show that TWO-MACHINE-SCHEDULING is N'P-complete by performing the following steps:

(a) 10 points. Show that the TWO-MACHING-SCHEDULING problem is in NP

(b) 15 points. Show how to reduce the PARTITION problem to the TWO-MACHINE- SCHEDULING problem. That is, show how to use an algorithm for solving the PARTITION problem to solve the TWO-MACHINE-SCHEDULING problem.