<p>Yes, this can be solved in polynomial time.  Here is an algorithm.</p>
<p>To rephrase the problem statement:</p>
<ul>
<li>We are given a basis <span class="math-container">$P_1,\dots,P_k \in \text{Sym}(n)$</span> of <span class="math-container">$k$</span> random permutations on <span class="math-container">$\{1,2,\dots,n\}$</span>.  We are also given a random permutation <span class="math-container">$Q \in \text{Sym}(n)$</span>, the target, and we want to find a product of a sequence of <span class="math-container">$P$</span>'s that yields <span class="math-container">$Q$</span>.  We want the total running time and the length of the sequence to be polynomial.</li>
</ul>
<p>The algorithm:</p>
<ul>
<li><p><strong>Step 1.</strong> Expand the basis so <span class="math-container">$k\ge 100 n^3$</span>.  This can be readily done: we take <span class="math-container">$b$</span> to be a bit larger than <span class="math-container">$2 \lg(100 n^3) + \lg(n!)$</span> and generate <span class="math-container">$100 n^3$</span> random length-<span class="math-container">$b$</span> sequences of basis elements.  Call the product of the <span class="math-container">$i$</span>th sequence <span class="math-container">$P'_i$</span>.  Note that the <span class="math-container">$P'_i$</span>'s look more or less like <span class="math-container">$100 n^3$</span> independent random permutations.  Thus, we can add all the <span class="math-container">$P'_i$</span>'s to the basis, and any sequence that uses the <span class="math-container">$P'_i$</span>'s can be re-expressed as a sequence over the <span class="math-container">$P_i$</span>'s (at the cost of increasing the sequence length by a factor <span class="math-container">$b$</span>).</p>
<p>After Step 1, we can assume that <span class="math-container">$k \ge 100 n^3$</span>.</p>
</li>
<li><p><strong>Step 2.</strong> Generate all transpositions <span class="math-container">$(i,j) \in \text{Sym}(n)$</span>.  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 <span class="math-container">$C(n,2)$</span> such transpositions, so we'll repeat the following step <span class="math-container">$C(n,2)$</span> times, once for each desired transposition.</p>
<p>Suppose we are trying to generate the transposition <span class="math-container">$(1,2)$</span>, i.e., the permutation that swaps 1 and 2 and leaves all other elements unchanged.  For simplicity, I'm going to assume <span class="math-container">$n$</span> is odd, but this can be generalized to even <span class="math-container">$n$</span>, too.  We're going to look for a basis element that is <em>good</em>.  Call a basis element <span class="math-container">$P$</span> <em>good</em> if the cycle structure of <span class="math-container">$P$</span> is <span class="math-container">$(1,2), (3,\dots)$</span>.  In other words, <span class="math-container">$P$</span> has to contain exactly two cycles: the 2-cycle <span class="math-container">$(1,2)$</span>, and a <span class="math-container">$n-2$</span>-cycle that visits all of the other elements.  Or, to put it another way, <span class="math-container">$P(1)=2$</span>, <span class="math-container">$P(2)=1$</span>, and the orbit of 3 is <span class="math-container">$\{3,4,\dots,n\}$</span>.  Note that if <span class="math-container">$P$</span> is good, then <span class="math-container">$P^{n-2}=(1,2)$</span>.  Also, a random permutation is good with probability <span class="math-container">$(n-3)!/n! \approx 1/n^3$</span>, so with high probability there is at least one good basis element.  Thus we can readily find a way to generate the transposition <span class="math-container">$(1,2)$</span> using a sequence of length <span class="math-container">$n-2$</span>.  By symmetry, we can do the same for any other transposition.  Repeating this procedure <span class="math-container">$n(n-1)/2$</span> times yields a way to generate all the transpositions.</p>
</li>
<li><p><strong>Step 3.</strong> Express <span class="math-container">$Q$</span> as a product of transpositions.  It is easy to express any permutation over <span class="math-container">$\{1,\dots,n\}$</span> as a product of at most <span class="math-container">$n$</span> transpositions: just find its cycle structure, then express each cycle of length <span class="math-container">$l$</span> as a product of <span class="math-container">$l-1$</span> 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 <span class="math-container">$Q$</span>, too.</p>
</li>
</ul>
<p>The length of the solution is something like <span class="math-container">$O(n^3 \lg n)$</span>.  The running time of the procedure is something like <span class="math-container">$O(n^5)$</span>.  This is all polynomial.</p>

CC BY-SA 3.0
2013-07-12T13:50:11.050Z
Wow! I will check it carefully.
SDL
CC BY-SA 3.0
2013-07-16T14:54:59.303Z
D.W.: Did you invent the algorithm yourself or the same problem was published somewhere else?
SDL
CC BY-SA 3.0
2013-07-16T18:05:46.187Z
@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.
CC BY-SA 3.0
2013-07-17T22:03:39.873Z
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
CC BY-SA 4.0
2018-11-27T20:14:26.180Z
Why would the additional basis elements act like $100 n^3$ independent random permutations?
qbt937
CC BY-SA 4.0
2018-11-28T07:54:04.803Z
@qbt937, that's a claim that I don't have a proof for, but which seems likely to be true to me.
D.W.
CC BY-SA 3.0
2013-07-10T20:45:33.353Z
2013-07-10T21:23:32.843Z
2020-06-17T09:38:08.363Z
D.W.
<p>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 <em><a href="http://pagesperso.lina.univ-nantes.fr/~bulteau-l/pdf/BFR-mfcs12.pdf" rel="nofollow">Pancake flipping problem</a></em> shows that finding the shortest possible sequence is NP-hard.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-07-04T12:52:39.337Z
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
CC BY-SA 3.0
2013-07-04T13:21:11.987Z
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
CC BY-SA 3.0
2013-07-04T14:10:51.550Z
@SDL: perhaps you can use an approach like the one described in http://www.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
CC BY-SA 3.0
2013-07-10T06:53:39.990Z
@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
CC BY-SA 3.0
2013-07-03T20:09:14.157Z
2013-07-10T06:57:45.083Z
2013-07-10T06:57:45.083Z
Marzio De Biasi
<p>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$.</p>

<p>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.</p>

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

<p>I suppose this problem, as $n$ grows, is exponential.</p>

<p>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.</p>

<p>It is related to any $\sf{NP}$-Complete problem?</p>

<p>Any idea? Thanks!</p>

CC BY-SA 3.0
2013-07-04T12:54:51.193Z
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
CC BY-SA 3.0
2013-07-05T13:07:08.310Z
Edit: Added the forgotten initial permutation $Q$
SDL
<permutations><np-complete>
Finding the identity with permutation chains
SDL
# Finding the identity with permutation chains

(Asked by: username_0 on 2013-07-03)

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!

**Tags:** permutations, np-complete

> **Comments:**
> **username_0**: 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.  
> **username_0**: Edit: Added the forgotten initial permutation $Q$  

---

## 2 answers

### Answer by username_1 on 2013-07-10. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: Wow! I will check it carefully.  
> **username_0**: username_1: Did you invent the algorithm yourself or the same problem was published somewhere else?  
> **username_1**: @username_0, 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!  
> **username_0**: 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.  
> **username_2**: Why would the additional basis elements act like $100 n^3$ independent random permutations?  
> **username_1**: @username_2, that's a claim that I don't have a proof for, but which seems likely to be true to me.  

---

### Answer by username_3 on 2013-07-03. Score: 4

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](http://pagesperso.lina.univ-nantes.fr/~bulteau-l/pdf/BFR-mfcs12.pdf)* 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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: @username_0: perhaps you can use an approach like the one described in http://www.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.  
> **username_3**: @username_1: 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.  

---

