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

Show that PERM-POWER ∈ P. Note that the most obvious algorithm doesn’t run within polynomial time. First try it where t is a power of 2.

Transcribed Image Text:

PERM-POWER = {{p,q, t)| p = q' where p and q are permutations on {1, ..., k} and t is a binary integer}.