A permutation on the set {1,..., k} is a one-to-one and onto function on this set. When p is a permutation, pt means the composition of p with itself t times. Let PERM-POWER be the language consisting of all encodings for which p and q are permutations (over {1,..., k}), and q = pt. Prove that PERM=POWER P, Hint: the obvious algorithm does not run in polynomial time since the problem size is logarithmic (and no linear) with respect to the value of t.