# 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

## 2 Answers

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