1
$\begingroup$

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.

  • 0
    Deleting the comments I made, I put them into an answer.2012-12-11

1 Answers 1

1

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.

  • 0
    Yep, you've got the r$i$ght idea. No problem, happy to help.2012-12-11