Problema de soma de subconjunto para permutações

Question

Dadas permutações $g_1,\,\ldots, g_m \in S_n$ de tamanho $n$ e permutação de destino $g \in S_n$, decida se existe um subconjunto de $\{g_1,\, \ldots, g_m\}$, cuja composição em alguma ordem (ou, alternativamente, como variante deste problema, na mesma ordem) é igual a $g$, ou seja $g_{i_1} \circ g_{i_2} \circ \cdots \circ g_{i_k} = g$.

Este é na verdade um problema de soma de subconjunto, mas pelo grupo simétrico $(S_n,\circ)$ em vez de $(\mathbb{Z}, +)$.

As perguntas são:

1. Existe uma solução conhecida em tempo polinomial?
2. Caso contrário, este problema é conhecido como NP-completo?

Eu encontrei um artigo sobre problemas de mochila em grupos, no entanto, esses resultados parecem não ser aplicáveis ​​para grupos simétricos.

Answer 1

Este problema, que chamarei de Subset-Perm-Sum, é NP-completo.A adesão é fácil:adivinhe o subconjunto de forma não determinística e depois verifique.

Para dureza pode-se reduzir de 3CNF-SAT de uma forma muito semelhante à prova padrão de dureza para Subset-Sum.

Deixar $\varphi$ seja uma fórmula de entrada com $v$ variáveis ​​e $c$ cláusulas.Construiremos uma instância de Subset-Perm-Sum sobre $S_{2v+4c}$.Para cada variável que construímos $2$ permutações (uma que representará a variável e outra que representará sua negação), e para cada cláusula construiremos $2$ permutações também.

Para cada cláusula $C_j, 1\leq j \leq c$ nós associamos $4$ elementos: $2v+4j-k$ para $0 \leq k \leq 3$.Para construir o $2$ permutações associadas a uma cláusula, simplesmente fazemos um ciclo nos seus elementos associados.Aquilo é, $$p(C_j) = (2v+4j-3, 2v+4j-2, 2v+4j-1, 2v+4j)$$ (vamos adicionar $2$ instancia de $p(C_j)$ ao conjunto, queremos encontrar uma soma de subconjunto mais tarde.)

Considere o $i$-ésima variável, $x_i$, e associe a ele os elementos $2i-1$ e $2i$ de $S_{2v+4c}$.Para construir a permutação $p(x_i)$ de variável $x_i$ simplesmente troque seus elementos associados ($2i-1$ e $2i$) e multiplique pela permutação de cada cláusula em que está contido.Então, em notação de ciclo você pode escrever:$$ p (x_i) = (2i-1, 2i) prod_ {j | x_i em c_j} p (c_j) $$

Considere agora o multiset $M$ essa é a união do $p(x_i)$ e $p(\bar{x_i})$ e duas vezes cada $p(C_j)$.

Nós definimos a permutação alvo $t$ como:

$$ t = prod_ {i = 1}^v (2i-1, 2i) cdot prod_ {j = 1}^cp (c_j)^3 $$

Alegar: Existe um subconjunto $X$ de $M$ que compõe a permutação alvo $t$ (deixe-me escrever $p(X)=t$) se e apenas se $\varphi$ é satisfatório.

Suponha tal $X$ existe, então sabemos $X$ contém exatamente um de $p(x_i)$ e $p(\bar{x}_i)$, pois é a única forma para a composição de $X$ incluir o ciclo $(2i-1, 2i)$.Além disso, podemos ver que para cada cláusula $C_j\in\varphi$, pelo menos uma variável if satisfaz, como ter $p(C_j)^3$ em $p(X)$ precisamos ter incluído um $p(\el_i)$ tal que literalmente $\el_i$ é em $C_j$.Observe que tomando as duas instâncias de $p(C_j)$ em $X$ não é o suficiente.Portanto, existe uma atribuição de variáveis ​​que satisfaz todas as cláusulas.Para a direção para trás, deixe $\sigma$ ser uma tarefa satisfatória de $\varphi$.Se $\sigma(x_i) = 1$ então deixamos $X$ conter $p(x_i)$ e caso contrário, deixamos que contenha $p(\bar{x}_i)$.Para cada cláusula $C_j$, sabemos que existem entre $0 \leq r_j \leq 2$ variáveis ​​nele que não são satisfeitas por $\sigma$, e adicionamos $r_j$ ocorrências de $p(C_j)$ para $X$, então desta forma $p(X)$ inclui $p(C_j)^3$.É claro que a composição $X$ é igual a $t$.

Answer 2

O problema da soma do subconjunto é ainda mais difícil (NP-HARD) para grupos especiais que você pode incorporar em $ s_n $ . Veja o papel que você vinculou na descrição do problema.

$ \ textbf {observação:} $ $ g $ pode ser escrito como combinação de elementos < span class="contêiner matemática"> $ \ {g_1, \ lDOTs, g_k \} $ se e somente se $ g \ in \ langle g_1, \ ldots, g_k \ rangle $ . Sob a suposição de que cada uma das $ g_i $ pode aparecer qualquer número de vezes.

A complexidade do problema depende da representação de entrada. Existem dois dois caminhos mais comumente usados, mesa de Cayley e conjunto de geração. Para tabela Cayley, veja este artigo para resultados. Leia o CGM (problema de associação Cayley) link

$ \ textbf {cgm} $

$ \ textbf {entrada:} $ um grupo $ g $ por sua mesa de Cayley, < span class="contêiner matemática"> $ x \ subseteq g $ e $ t \ in g $ .

$ \ textbf {saída:} $ faz $ t $ pertence ao subgrupo $ \ langer x \ rangle $ gerado por $ x $ ?

No problema geral é no espaço de log simétrico.

---

$ \ langer A \ Rangle $ significa subgrupo gerado por $ a $