How would you go about proving that the above two problems


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.

Request for Solution File

Ask an Expert for Answer!!
Computer Network Security: How would you go about proving that the above two problems
Reference No:- TGS0972136

Expected delivery within 24 Hours