# Finding the identity with permutation chains

I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$.

How hard is to find a sequence $s(j)$ of $U$ subscripts in $[1..K]$, such that $P_{s1}(P_{s2}(...(P_{sU}(Q(i))))) = i$ for every $1\leq i \leq n$, where Q is an initial random permutation.

In other words, the composition of a subset of the given permutations must be the inverse of $Q$.

I suppose this problem, as $n$ grows, is exponential.

Note: the result must be the list of $s(j)$ values, and that list should be polynomial to $n$ in size. I cannot accept something like "apply P1 2^456 times" as an answer.

It is related to any $\sf{NP}$-Complete problem?

Any idea? Thanks!

• There also the possibility that the problem has no solution for a polynomially bounded number of permutations, and so there is a decision problem involved. – SDL Jul 4 '13 at 12:54
• Edit: Added the forgotten initial permutation $Q$ – SDL Jul 5 '13 at 13:07
• You have more comments at $\:$ crypto.stackexchange.com/questions/5234 . $\hspace{.83 in}$ – user6973 Jul 8 '13 at 3:35

Yes, this can be solved in polynomial time. Here is an algorithm.

To rephrase the problem statement:

• We are given a basis $P_1,\dots,P_k \in \text{Sym}(n)$ of $k$ random permutations on $\{1,2,\dots,n\}$. We are also given a random permutation $Q \in \text{Sym}(n)$, the target, and we want to find a product of a sequence of $P$'s that yields $Q$. We want the total running time and the length of the sequence to be polynomial.

The algorithm:

• Step 1. Expand the basis so $k\ge 100 n^3$. This can be readily done: we take $b$ to be a bit larger than $2 \lg(100 n^3) + \lg(n!)$ and generate $100 n^3$ random length-$b$ sequences of basis elements. Call the product of the $i$th sequence $P'_i$. Note that the $P'_i$'s look more or less like $100 n^3$ independent random permutations. Thus, we can add all the $P'_i$'s to the basis, and any sequence that uses the $P'_i$'s can be re-expressed as a sequence over the $P_i$'s (at the cost of increasing the sequence length by a factor $b$).

After Step 1, we can assume that $k \ge 100 n^3$.

• Step 2. Generate all transpositions $(i,j) \in \text{Sym}(n)$. We'll treat each such transposition as the target and find a way to express it as a product over the basis elements. There are $C(n,2)$ such transpositions, so we'll repeat the following step $C(n,2)$ times, once for each desired transposition.

Suppose we are trying to generate the transposition $(1,2)$, i.e., the permutation that swaps 1 and 2 and leaves all other elements unchanged. For simplicity, I'm going to assume $n$ is odd, but this can be generalized to even $n$, too. We're going to look for a basis element that is good. Call a basis element $P$ good if the cycle structure of $P$ is $(1,2), (3,\dots)$. In other words, $P$ has to contain exactly two cycles: the 2-cycle $(1,2)$, and a $n-2$-cycle that visits all of the other elements. Or, to put it another way, $P(1)=2$, $P(2)=1$, and the orbit of 3 is $\{3,4,\dots,n\}$. Note that if $P$ is good, then $P^{n-2}=(1,2)$. Also, a random permutation is good with probability $(n-3)!/n! \approx 1/n^3$, so with high probability there is at least one good basis element. Thus we can readily find a way to generate the transposition $(1,2)$ using a sequence of length $n-2$. By symmetry, we can do the same for any other transposition. Repeating this procedure $n(n-1)/2$ times yields a way to generate all the transpositions.

• Step 3. Express $Q$ as a product of transpositions. It is easy to express any permutation over $\{1,\dots,n\}$ as a product of at most $n$ transpositions: just find its cycle structure, then express each cycle of length $l$ as a product of $l-1$ transpositions. Since in step 2 we figured out how to express each transposition as a product over the basis elements, this gives us a way to express $Q$, too.

The length of the solution is something like $O(n^3 \lg n)$. The running time of the procedure is something like $O(n^5)$. This is all polynomial.

• Wow! I will check it carefully. – SDL Jul 12 '13 at 13:50
• D.W.: Did you invent the algorithm yourself or the same problem was published somewhere else? – SDL Jul 16 '13 at 14:54
• @SDL, this is my invention. I have not seen this anywhere before (though I would not be surprised to learn that others have discovered it before). Thank you for the fun problem! – D.W. Jul 16 '13 at 18:05
• It is not only fun. It's related to my toy NanoHash crypto hashing algorithm. It's is so small, just about 50 lines of code. It is 4 times slower than SHA-2 though and it does data-dependent memory accesses. I will post about it soon. – SDL Jul 17 '13 at 22:03
• Why would the additional basis elements act like $100 n^3$ independent random permutations? – qbt937 Nov 27 '18 at 20:14

Just a note: if the $K$ permutations can be arbitrary, and if you want to find the shortest possible solution, a quick reduction from the Pancake flipping problem shows that finding the shortest possible sequence is NP-hard.

The reduction: Given an instance of the Pancake flipping (i.e. a permutation of $[1..n]$), add to the list the $K = n$ possible prefix permutations. The application of a $P_i$ corresponds to a pancake flip, and $U$ of them can generate the identity permutation if and only if the pancake of the original problem can be sorted using $U$ flips.

However, this doesn't apply directly to the problem as you stated it. If we don't need the shortest possible solution, it's easy to find a solution of length $O(n)$ to the pancake flipping problem. Since this question asked for any solution (rather than the shortest possible solution), there's no proof that this problem is NP-hard.

• Interesting. I will read the paper. But the permutations are random, so in the average case my problem might be much easy to solve. Nevertheless, it's a good starting point. – SDL Jul 4 '13 at 12:52
• Pancake permutations are self-reversible (each own is it's own inverse). Generally a random permutation Pi will not be it's own inverse, nor the inverse of another Pj with i!=j. – SDL Jul 4 '13 at 13:21
• @SDL: perhaps you can use an approach like the one described in scottaaronson.com/blog/?p=469 for 3SAT. In particular it could be interesting to study how to pick $K$ (given $n$) such that the problem almost certainly has a solution. – Marzio De Biasi Jul 4 '13 at 14:10
• @D.W.: indeed I wrote "Just a note" ... the solution of the Pancake problem can be found in $O(n)$ (Gates, Papadimitriou), as explained in the linked paper. But you are right it needs a clarification. – Marzio De Biasi Jul 10 '13 at 6:53