4. [20 points] For any fixed integer k > 2, the k-PARTITION PROBLEM (abbreviated k-PP') is: given a sequence of positive integers (w, w2,... ,wn), is it possible to partition them into k groups having equal sums. More formally, is there an n-vector h each of whose entries is a integer in the range 1,..., k such that, for each 1SjSk: wis Eh where h l-i hli j. For example, (1,2,1,3,1,1) is a "yes" instance of 3-PP, but a "no" instance of 4-PP; (3, 2,1,3, 3) is the reverse. (a) As in the previous problem, carefully show that k-PP is in NP. (b) Give an algorithm for k-PP and analyze its running time (c) Show that 2-PP Sp KNAP (slide 36). (Make sure all the pieces required by my definition of reduction slide 33-are carefully explained.) (d) Suppose I could show that there is no polynomial time algorithm for KNAP. Would this together with 4c imply that there cannot be a polynomial time algorithm for 2-PP? Explain why or why not. (e) Extra Credit: Show KNAP

2, Hint: start with k-2. 4. [20 points] For any fixed integer k > 2, the k-PARTITION PROBLEM (abbreviated k-PP') is: given a sequence of positive integers (w, w2,... ,wn), is it possible to partition them into k groups having equal sums. More formally, is there an n-vector h each of whose entries is a integer in the range 1,..., k such that, for each 1SjSk: wis Eh where h l-i hli j. For example, (1,2,1,3,1,1) is a "yes" instance of 3-PP, but a "no" instance of 4-PP; (3, 2,1,3, 3) is the reverse. (a) As in the previous problem, carefully show that k-PP is in NP. (b) Give an algorithm for k-PP and analyze its running time (c) Show that 2-PP Sp KNAP (slide 36). (Make sure all the pieces required by my definition of reduction slide 33-are carefully explained.) (d) Suppose I could show that there is no polynomial time algorithm for KNAP. Would this together with 4c imply that there cannot be a polynomial time algorithm for 2-PP? Explain why or why not. (e) Extra Credit: Show KNAP

2, Hint: start with k-2