9
$\begingroup$

Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, alternatively, as a variant of this problem, in the same order) is equal to $g$, i.e. $g_{i_1} \circ g_{i_2} \circ \cdots \circ g_{i_k} = g$.

This is actually a subset sum problem, but for symmetric group $(S_n, \circ)$ instead of $(\mathbb{Z}, +)$.

The questions are:

  1. Is there a known solution in polynomial time?
  2. Otherwise, is this problem known as NP-complete?

I've found a paper on knapsack problems in groups, however, these results seems to be not applicable for symmetric group.

$\endgroup$
  • 3
    $\begingroup$ To be 100% clear: just like in Subset Sum, you aren't allowed to reuse the same permutation more than once, right? If you're allowed to reuse permuations from the input set then it's a problem about generators rather than a Subset Sum analogue. $\endgroup$ – Aaron Rotenberg Dec 28 '19 at 4:48
  • $\begingroup$ @AaronRotenberg You can also consider a variant of this problem in which we are allowed to reuse the same permutation more than once, if you think this variant would be easier. $\endgroup$ – Nastya Koroleva Dec 29 '19 at 14:42
  • 2
    $\begingroup$ The variant where you are allowed to reuse permutations is called permutation group membership testing and can be solved in polynomial time by a classic algorithm based on subgroup chains. See Furst, Hopcroft, and Luks. "Polynomial Time Algoirthms for Permutation Groups." (Or any modern source on algorithms for finite groups, I'm guessing.) $\endgroup$ – Aaron Rotenberg Dec 29 '19 at 19:50
  • 1
    $\begingroup$ Permutation group membership testing is not really analogous to a knapsack problem because every element of a finite group has a finite order: if $x$ is available, so is $x^{-1}$, by just stringing together $\operatorname{ord}(x) - 1$ copies of $x$. $\endgroup$ – Aaron Rotenberg Dec 29 '19 at 19:57
2
$\begingroup$

The subset sum problem is even harder(NP-hard) for special groups which you can embed into $S_n$. See the paper you have linked in the problem description.

$\textbf{Observation:}$ $g$ can be writtens as combination of elements $\{g_1,\ldots,g_k\}$ if and only if $g \in \langle g_1,\ldots,g_k\rangle$. Under the assumption that each of $g_i$ can appears any number of times.

The complexity of the problem depends upon the input representation. There are two two most commonly used ways, Cayley table and generating set. For Cayley table see this paper for results. Read the CGM(Cayley membership problem) Link

$\textbf{CGM} $

$\textbf{Input :}$ A group $G$ by its Cayley table, $X \subseteq G$ and $t \in G$.

$\textbf{Output :}$ Does $t$ belong to the subgroup $\langle X \rangle$ generated by $X$?

In general problem is in Symmetric log space.


$\langle A \rangle$ means subgroup generated by $A$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not sure if this is exactly right, because I suspect in the original problem no group element can be used more than once. You can have $g \in \langle g_1,\dots,g_k \rangle$ but there is no way to obtain $g$ by a composition of a subset of the $g_i$'s if you are restricted to using each only once. Therefore, I'm not convinced the problem is equivalent to CGM. $\endgroup$ – D.W. Dec 28 '19 at 6:02
  • $\begingroup$ @D.W Ok Let me edit the answer. $\endgroup$ – Shiv Dec 28 '19 at 6:18
  • $\begingroup$ It seems the SSP problem defined in that paper is not allowed to change the order of the given elements, which is different from OP's problem. $\endgroup$ – xskxzr Dec 28 '19 at 15:04
  • 1
    $\begingroup$ @aaag Well, the size of Cayley table of $S_n$ is $O((n!)^2)$, which is actually too big to build, therefore I think this doesn't answers if there exists a polynomial time algorithm for original problem, nor provides an evidence of NP-completeness. Am I right? $\endgroup$ – Nastya Koroleva Dec 29 '19 at 14:23
  • $\begingroup$ @aaag "for special groups which you can embed into $S_n$" — for which groups? It seems that every special group mentioned in the paper is infinite, however all $S_n$'s are finite. $\endgroup$ – Nastya Koroleva Jan 3 at 19:22

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.