1. The 3-Partition problem is defined as follows. Given a finite set A of 3m elements, a bound B ? Z+ (a positive integer) and a size s(a) ? Z+ for each element a ? A such that s(a) satisfies the following inequalities: B/4 < s(a) < B/2 and such that
a?A∑ s(a) = mB.
Can A be partitioned into m disjoint sets S1, S2, ..., Sm such that, for 1 ≤ i ≤ m,
a?S∑ s(a) = B?
Describe a nondeterministic polynomial time algorithm for this problem.
(c) How would you go about proving that the above two problems are indeed NP-Complete?
(d) If Professor Weise arrives at describing a deterministic polynomial algorithm for any of the above problems, what conclusions would you draw? Justify your answer.