Sous-ensemble SUM Problème de permutations

Question

Permutations données $ g_1, \, \ ldots, g_m \ in s_n $ de taille $ n $ et la permutation cible $ g \ in s_n $ , décidez s'il existe un sous-ensemble de $ \ {g_1, \, \ ldots, g_m \} $ , quelle composition dans une commande (ou, en variante, en tant que variante de ce problème, dans le même ordre) est égal à $ g $ < / span>, c'est-à-dire $ g_ {i_1} \ circ g_ {i_2} \ circ \ CDOT \ circ g_ {i_k}= g $

.

.

Ceci est en fait un Sous-ensemble Problème , mais pour Groupe symétrique $ (s_n, \ circ) $ au lieu de < Span Classe="Math-Conteneur"> $ (\ mathbb {z}, +) $ .

Les questions sont:

1. y a-t-il une solution connue en temps polynomial?
2. Sinon, ce problème est-il appelé NP-complet?

J'ai trouvé un papier sur Problèmes de Knapsack dans les groupes , cependant, ces résultats semblent être Non applicable pour le groupe symétrique.

Answer 1

Ce problème, que j'appellerai sous-ensemble-Sum, est NP-complet. L'adhésion est facile: devinez le sous-ensemble non déterministe, puis vérifiez.

Pour la dureté, on peut réduire de 3cnf-si similaire à la preuve de dureté standard de la dureté pour la somme sous-ensemble.

let $ \ varphi $ être une formule d'entrée avec $ v $ variables et $ C $ clauses. Nous construirons une instance de sous-ensemble-somme sur $ s_ {2v + 4c} $ . Pour chaque variable, nous construisons $ 2 $ permutations (une qui représentera la variable et celui qui représentera sa négation), et pour chaque clause, nous construirons 2 $ $ Permutations également.

à chaque clause $ C_J, 1 \ LEQ J \ LEQ C $ Nous associions 4 $ éléments : $ 2V + 4J-k $ pour $ 0 \ LEQ K \ LEQ 3 $ . Pour construire la 2 $ $ Permutations associées à une clause Nous faisons simplement un cycle sur ses éléments associés. C'est-à-dire $$ p (c_j)= (2V + 4J-3, 2V + 4J-2, 2V + 4J-1, 2V + 4J) $$ ( nous ajouterons $ 2 $ $ instance de $ p (c_j) $ à l'ensemble Nous voulons trouver un sous-ensemble -sum plus tard.)

considérer la $ i $ -th variable, $ x_i $ et associez-y les éléments 2i-1 $ et $ 2i $ de $ s_ {2V + 4c} $ . Pour construire la permutation $ p (x_i) $ de variable $ x_i $ échangez simplement ses éléments associés (< span class="math-conteneur"> $ 2I-1 $ et $ 2i $ ) et multiplie par la permutation de chaque clause qu'il contient dans . Ensuite, dans la notation de cycle, vous pouvez écrire: $$ p (x_i)= (2i-1, 2i) \ prod_ {j | x_i \ in c_j} p (c_j) $$

Considérez maintenant le multiset $ M $ C'est l'union de la $ P (x_i) $ et $ p (\ bar {x_i}) $ et deux fois chacun de chaque $ p (c_j) $ .

Nous définissons la permutation cible $ t $ comme:

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

réclamation: il y a un sous-ensemble $ x $ de $ m $ Cela compose à la permutation cible $ t $ (laissez-moi écrire $ p (x)= t $ ) Si et seulement si $ \ VARPHI $ est satisfiablement.

assumer une telle $ x $ existe, alors nous savons $ x $ contient exactement un $ p (x_i) $ et $ p (\ bar {x} _i) $ , telle qu'elle est Le seul moyen de la composition de $ x $ pour inclure le cycle $ (2i-1, 2i) $ . En outre, nous pouvons voir que pour chaque clause $ C_J \ in \ Varphi $ , au moins une si les variables le satisfont, d'avoir $ p (c_j) ^ 3 $ in $ p (x) $ nous devons avoir inclus une $ p (\ ell_i) $ tel que littéral $ \ ell_i $ est dans $ C_J $ . Notez que prendre les deux instances de $ p (c_j) $ in $ x $ n'est pas suffisant. Par conséquent, il y a une affectation de variables qui répondent à chaque clause. Pour la direction arrière, laissez $ \ sigma $ être une affectation satisfaisante de $ \ varphi $ . Si $ \ SIGMA (X_I)= 1 $ Nous laissons $ x $ contient $ p (x_i) $ et sinon nous le laissons contenir contenir $ p (\ bar {x} _i) $ . Pour chaque clause $ C_J $ , nous savons qu'il existe entre $ 0 \ LEQ R_J \ LEQ 2 $ variables sur Il n'est pas satisfait de $ \ sigma $ , et nous ajoutons $ r_j $ occurrences de $ p (c_j) $ à $ x $ , donc de sorte $ p (x) $ inclut $ p (c_j) ^ 3 $ . Il est clair que la composition de

Tainer "> $ x $ est égal à $ t $ .

Answer 2

Le problème du sous-ensemble est encore plus difficile (NP-DUR) pour des groupes spéciaux que vous pouvez intégrer dans $ s_n $ . Voir le papier que vous avez lié dans la description du problème.

$ \ textbf {Observation:} $ $ g $ peut être des écrivains comme une combinaison d'éléments < span class="math-conteneur"> $ \ {g_1, \ ldots, g_k \} $ si et seulement si $ g_1 in \ ldots g_1, \ ldots, g_k \ rangs $ . Sous l'hypothèse que chacun de $ g_i $ peut apparaître n'importe quel nombre de fois.

La complexité du problème dépend de la représentation des intrants. Il y a deux manières de deux les plus couramment utilisées, la table de Cayley et le groupe de génération de Cayley. Pour la table de Cayley, voir cet article pour les résultats. Lisez le CGM (problème d'adhésion à CAYLEY) LINK

$ \ textbf {cgm} $

$ \ textbf {entrée:} $ un groupe $ g $ par sa table de Cayley, < SPAN CLASS="MATH-CONTENANT"> $ X \ SOUSETEQ G $ et $ T \ IN G $ .

.

$ \ textbf {sortie:} $ fait $ t $ appartient au sous-groupe $ \ lambes x \ rangs $ généré par $ x $ ?

dans le problème général est dans l'espace logiciel symétrique.

---

$ \ lelopper A \ RANG $ $ signifie généré par $ A $