3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SDL Jul 4 '13 at 12:54
  • $\begingroup$ Edit: Added the forgotten initial permutation $Q$ $\endgroup$ – SDL Jul 5 '13 at 13:07
  • 1
    $\begingroup$ You have more comments at $\:$ crypto.stackexchange.com/questions/5234 . $\hspace{.83 in}$ $\endgroup$ – user6973 Jul 8 '13 at 3:35
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow! I will check it carefully. $\endgroup$ – SDL Jul 12 '13 at 13:50
  • $\begingroup$ D.W.: Did you invent the algorithm yourself or the same problem was published somewhere else? $\endgroup$ – SDL Jul 16 '13 at 14:54
  • $\begingroup$ @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! $\endgroup$ – D.W. Jul 16 '13 at 18:05
  • $\begingroup$ 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. $\endgroup$ – SDL Jul 17 '13 at 22:03
  • $\begingroup$ Why would the additional basis elements act like $100 n^3$ independent random permutations? $\endgroup$ – qbt937 Nov 27 '18 at 20:14
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SDL Jul 4 '13 at 12:52
  • $\begingroup$ 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. $\endgroup$ – SDL Jul 4 '13 at 13:21
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Jul 4 '13 at 14:10
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Jul 10 '13 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.