6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – David Richerby May 30 '15 at 8:14
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$\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$

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

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.