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
  • 3
    $\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
  • 2
    $\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$

This problem, that I will call Subset-Perm-Sum, is NP-complete. Membership is easy: guess the subset non-deterministically and then check.

For hardness one can reduce from 3CNF-SAT in a very similar way to the standard proof of hardness for Subset-Sum.

Let $\varphi$ be an input formula with $v$ variables and $c$ clauses. We will build an instance of Subset-Perm-Sum over $S_{2v+4c}$. For every variable we build $2$ permutations (one that will represent the variable, and one that will represent its negation), and for every clause we will build $2$ permutations as well.

To each clause $C_j, 1\leq j \leq c$ we associate $4$ elements: $2v+4j-k$ for $0 \leq k \leq 3$. To build the $2$ permutations associated to a clause we simply do a cycle on its associated elements. That is, $$ p(C_j) = (2v+4j-3, 2v+4j-2, 2v+4j-1, 2v+4j)$$ (we will add $2$ instance of $p(C_j)$ to the set we want to find a subset-sum later.)

Consider the $i$-th variable, $x_i$, and associate with it the elements $2i-1$ and $2i$ of $S_{2v+4c}$. To build the permutation $p(x_i)$ of variable $x_i$ simply swap its associated elements ($2i-1$ and $2i$), and multiply by the permutation of each clause it is contained in. Then, in cycle notation you can write: $$ p(x_i) = (2i-1, 2i) \prod_{j | x_i \in C_j}p(C_j) $$

Consider now the multiset $M$ that is the union of the $p(x_i)$ and $p(\bar{x_i})$ and two times each $p(C_j)$.

We define the target permutation $t$ as:

$$ t = \prod_{i=1}^v (2i-1, 2i) \cdot \prod_{j=1}^c p(C_j)^3 $$

Claim: There is a subset $X$ of $M$ that composes to the target permutation $t$ (let me write $p(X)=t$) if and only if $\varphi$ is satisfiable.

Assume such an $X$ exists, then we know $X$ contains exactly one out of $p(x_i)$ and $p(\bar{x}_i)$, as it is the only way for the composition of $X$ to include the cycle $(2i-1, 2i)$. Furthermore, we can see that for each clause $C_j \in \varphi$, at least one if variables satisfies it, as to have $p(C_j)^3$ in $p(X)$ we need to have included a $p(\ell_i)$ such that literal $\ell_i$ is in $C_j$. Note that taking the two instances of $p(C_j)$ in $X$ is not enough. Therefore, there is an assignment of variables that satisfies every clause. For the backward direction, let $\sigma$ be a satisfying assignment of $\varphi$. If $\sigma(x_i) = 1$ then we let $X$ contain $p(x_i)$ and otherwise we let it contain $p(\bar{x}_i)$. For each clause $C_j$, we know there are between $0 \leq r_j \leq 2$ variables on it that are not satisfied by $\sigma$, and we add $r_j$ occurrences of $p(C_j)$ to $X$, so this way $p(X)$ includes $p(C_j)^3$. It is clear that the composition of $X$ equals $t$.

| cite | improve this answer | |
$\endgroup$
1
$\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$ – user35837 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.