# Proof that computing composition of permutations is in P

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.

-
This might be a starting point for understanding permutations as operations rather than arrangements. You may also need to learn about the cycle decomposition of a permutation to find a polynomial-time algorithm for this. –  joriki Dec 11 '12 at 0:04
Deleting the comments I made, I put them into an answer. –  John Moeller Dec 11 '12 at 0:33

I think I babbled enough for a full answer, so I'll put what I commented above in an answer (and deleting the comments):

If it helps your understanding, permutations form a group. For example, if you're talking about permutations of $\{1,2,3\}$, then $\{1,2,3\}$ is the identity (it doesn't shuffle anything). $\{1,3,2\}$, on the other hand, swaps the last two elements of whatever you give it. So $\{1,3,2\}^2=\{1,3,2\}\{1,3,2\}=\{1,2,3\}$. This makes sense because swapping two things twice shouldn't have any effect. Similarly, "rolling" the whole list should get back to the same elements when done three times in a row: $\{2,3,1\}^3=\{1,2,3\}$.

"Composing" in the permutation setting just means "do one permutation and then the other." But this is just another permutation. Say we have some list $\{a,b,c\}$, and we permute it by $\{1,2,3\}$ and then by $\{3,2,1\}$. The first says "put the first first, the second second, and the third third." In other words, do nothing. The second says, "put the third first, the second second, and the first third." So if you do these in order, you get $\{c,b,a\}$.

But you can think of the first permutation as "standing in" for the list it operates on, so you can describe the composition of two permutations purely by the action they do together. $\{3,2,1\}$ operates on $\{1,2,3\}$ by swapping the first and last, so you get one permutation $\{3,2,1\}$ that does the same thing to the list: it makes $\{c,b,a\}$.

You can verify yourself that $\{2,3,1\}\{2,1,3\}$ does the same thing as $\{3,2,1\}$.

Getting back to the algorithm:

The naive version would just multiply $q$ by itself $t$ times. Remember that to be in $P$, a language has to be polynomial in the size of the input. The naive algorithm is not polynomial because $t$ is exponential in $\textrm{size}(t)=O(\log(t))$. You have to do better than that for $P$.

One attack to your problem is to take the hint in the description: $\{\dots \textrm{and }t\textrm{ is a binary integer}\}$. Think modulo exponentiation in the RSA algorithm.

-
This explanation makes really strong intuitive sense. Thanks a lot, John. I still have the rest of the proof to good through and I think I have a good enough understanding to play around with it. It's still pretty vague, but as I understand it, the key is to $mod2$ both sides (ie. $p mod2 = q^t mod2$) and use modulo exponentiation from there. –  David Chouinard Dec 11 '12 at 3:12
Kind of. But what I really suggest is to look at exponentiation of integers modulo some prime, and see how the exponentiation is done without repeating the multiplication $t$ times. There's a neat trick you can use with the binary representation of $t$. That same trick applies to permutations. –  John Moeller Dec 11 '12 at 3:17
Ah, it seems that the "right-to-left binary method" is what I need (en.wikipedia.org/wiki/…). I'll read up on that. Once again, thanks a lot for your tremendous help, John. –  David Chouinard Dec 11 '12 at 3:31
Yep, you've got the right idea. No problem, happy to help. –  John Moeller Dec 11 '12 at 4:08