1. (Exercise 8.23 from Kleinberg & Tardos) Given a set of nnite binary strings S = {s1 . , sk}, we say that a string u is a concatenation over s if it is equal to sisi . sit for some indices 11, ,2 E {1, ,k} A friend of yours is considering the following problem: Given two sets of finite binary strings, A = {a1, , am} and B = {b1, , bn), does there exist any string u so that u is both a concatenation over A and a concatenation over B? Your friend announces, "At least the problem is in NP, since I would just have to exhibit such a string u in order to prove the answer is yes." You point out (politely, of course) that this is a completely inadequate explanation; how do we know that the shortest such string u doesn't have length exponential in the size of the input, in which case it would not be a polynomial-size certiciate? However, it turns out that this claim can be turned into a proof of membership in NP. Specifically, prove the following statement. If there is a string u that is a concatenation over both A and B, then there is such a string whose length is bounded bu a polunomial in the sum of the lengths of the strings in AU B 1. (Exercise 8.23 from Kleinberg & Tardos) Given a set of nnite binary strings S = {s1 . , sk}, we say that a string u is a concatenation over s if it is equal to sisi . sit for some indices 11, ,2 E {1, ,k} A friend of yours is considering the following problem: Given two sets of finite binary strings, A = {a1, , am} and B = {b1, , bn), does there exist any string u so that u is both a concatenation over A and a concatenation over B? Your friend announces, "At least the problem is in NP, since I would just have to exhibit such a string u in order to prove the answer is yes." You point out (politely, of course) that this is a completely inadequate explanation; how do we know that the shortest such string u doesn't have length exponential in the size of the input, in which case it would not be a polynomial-size certiciate? However, it turns out that this claim can be turned into a proof of membership in NP. Specifically, prove the following statement. If there is a string u that is a concatenation over both A and B, then there is such a string whose length is bounded bu a polunomial in the sum of the lengths of the strings in AU B