Consider the following problem:
A permutation on the set ${1,…,k}$ is a one-to-one, onto function on this set. When $p$ is a permutation, $p^t$ means the composition of $p$ with itself $t$ times. Let $ PERM-POWER = \{⟨p, q, t⟩ | p = q^t \text{ where } p \text{ and } q \text{ are premutations on } \{1,…,k\} \text{ and } t \text{ is a binary integer}\} $ Show that $PERM-POWER \in P$. (Note that the most obvious algorithm doesn't run within polynomial time. Hint: First try it where $t$ is a power of 2.)
I don't even have a basic grasp of this problem. I understand what a permutation is and I understand the general concept of composition, but I don't see how the two are related. (if the permutations of the set {1,2,3} are {1,2,3}, {3,2,1}, etc., what's a composition of those things? I have a sense I'm missing an understanding of some very obvious concepts)
I suppose I'll be able to takle the rest of the proof once I understand that, but it seems daunting. Any more help is highly appreciated. Perhaps providing the naive non-polynomial algorithm or tips on the solution would be helpful.
Thank you.