Subset sum problem for permutations

Question

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.

Answer 1

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

Answer 2

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$