# Algorithm to compose identity from a set of permutations

Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity permutation?

• This is closely related to the word problem for finite groups, except that you're not restricting your set of permutations to be a group and you're looking for the shortest word equivalent to the identity. (Note that there are infinite groups with finite descriptions whose word problem is undecidable but I guess you're only dealing with finite sets of permutations.) – David Richerby May 30 '15 at 8:14

Assuming that "smallest composition" means smallest number of permutations used in the composition, then the NP-complete Pancake Flipping Problem is a special case of your problem.

$$\mathcal{PRODUCT-PARTITION}$$ is strongly $$\mathrm{NP}$$-hard as shown by Ng et al.

If you allow the representation of a permutation over $$\mathbb{Z}^{*}_p$$ to be almost-unary: except for one permutation, every other is given by the multiplier $$a\in\mathbb{Z}^{*}_p$$ in unary. And lastly, $$p$$ itself is given in binary. The only one other permutation is given by its multiplier $$A\in\mathbb{Z}^{*}_p$$ in binary, then your problem is $$\mathrm{NP}$$-hard.

Now, we show that $$\mathcal{PRODUCT-PARTITION}$$ can be reduced to our problem $$\mathcal{PERM-IDENTITY}$$.

Theorem: $$\mathcal{PRODUCT-PARTITION}\leq_p\mathcal{PERM-IDENTITY}$$

Proof: Given an instance $$\{a_1,\:a_2,\:\dots,\: a_n\}$$ of $$\mathcal{PRODUCT-PARTITION}$$, we show how to construct an instance of $$\mathcal{PERM-IDENTITY}$$.

Since all the $$a_i$$'s are given in unary (thanks to strong hardness), we are able to, in polynomial time, construct a prime $$q$$ (in unary) that is bigger any prime divisor of all the $$a_i$$'s. By $$\Pi$$, we denote the product of all the $$a_i$$'s. We can assume $$\Pi$$ to be a square number and that no $$a_i$$ is equal to $$1$$. Taking the modulus to be some big enough $$k$$th power of $$q$$ such that $$p=q^k>\Pi$$. All the following is done modulo $$p$$.

Now, we transform each $$a_i$$ to a permutation $$\pi_i$$ over $$\{0, 1, \dots, p-1\}$$ that describes the operation of multiplying with $$a_i$$ over $$\mathbb{Z}_p$$.

Now, the produced instance of our problem is $$\{\pi_1, \:\pi_2, \:\dots, \:\pi_n,\:sqrt(\Pi)^{-1}\}$$ (modulo $$p$$) (actually, the last one should be the corresponding permutation of $$sqrt(\Pi)^{-1}$$, but abusing the notation a little bit may not be quite harmful here).

If the given $$\mathcal{PRODUCT-PARTITION}$$ instance is a $$\mathrm{YES}$$ instance, then by taking the set of permutations corresponding to the set of numbers in the solution to the $$\mathcal{PRODUCT-PARTITION}$$ instance and $$sqrt(\Pi)^{-1}$$, we can easily see that the produced instance is a $$\mathrm{YES}$$ instance of $$\mathcal{PERM-IDENTITY}$$.

Conversely, if the produced instance of $$\mathcal{PERM-IDENTITY}$$ is a $$\mathrm{YES}$$ instance, then note that the product of any subset of the $$n$$ permutations corresponding to $$a_i$$ is quite small to $$p$$ (in the magnitude of their corresponding natural numbers). So, in order for the product to be $$1\:\mathrm{mod}\:p$$, the last permutation corresponding to $$sqrt(\Pi)^{-1}$$ (which is somehow bigger than the $$a_i$$'s) must be taken. Then, the set of $$a_i$$'s corresponding to the rest of the solution to the produced instance of $$\mathcal{PERM-IDENTITY}$$ problem must multiply up to exactly $$sqrt(\Pi)$$ (which is somehow similar in magnitude to the $$a_i$$'s). Thus, the given $$\mathcal{PRODUCT-PARTITION}$$ instance is a $$\mathrm{YES}$$ instance.$$\square$$

• What is PRODUCT-PARTITION? – Yuval Filmus Sep 24 '18 at 16:06
• Also, it's $\mathcal{REALLY\ HARD}$ to read all those script-font problem names. \textsc{...} (small caps) is much more legible. – David Richerby Sep 24 '18 at 17:42