Subset-Summenproblem für Permutationen

Question

gegebene Permutationen $ g_1, \, \ ldots, g_m \ in s_n $ der Größe $ n $ und Ziel-Permutation $ g \ in S_N $ , entscheiden Sie, ob eine Teilmenge von $ \ {G_1, \, \ vorhanden ist ldots, g_m \} $ , welche Komposition in einiger Reihenfolge (oder alternativ als Variante dieses Problems in derselben Reihenfolge) gleich $ G $ , dh $ g_ {i_1} \ circ g_ {i_2} \ circ \ cdopts \ circ g_ {i_k}= g $ .

Dies ist eigentlich ein Subset Summe Problem , aber für symmetrische Gruppe $ (s_n, \ circ) $ statt < Span-Klasse="Math-Container"> $ (\ mathbb {z}, +) $ .

Die Fragen sind:

.
1. Gibt es in der Polynomialzeit eine bekannte Lösung?
2. Andernfalls ist dieses Problem als NP-Complete bekannt?

Ich habe ein Papier auf

Answer 1

Dieses Problem, dass ich Subset-Perm-Sum-Summe nennen werde, ist np-komplett. Die Mitgliedschaft ist einfach: Erraten Sie die Teilmenge nicht deterministisch und prüfen Sie dann.

für die Härte kann man von 3cnf saß, saß auf sehr ähnliche Weise mit dem Standardnachweis der Härte für die Subset-Summe.

let $ \ varphi $ Seien Sie eine Eingabeformel mit $ V $ Variablen und $ C $ Klauseln. Wir erstellen eine Instanz von Subset-Perm-Sum-Summen über $ s_ {2v + 4c} $ . Für jede Variable erstellen wir $ 2 $ Permutationen (eine, die die Variable darstellt, und einer, der seine Negation darstellt), und für jede Klausel bauen wir $ 2 $ Permutationen.

zu jeder Klausel $ C_J, 1 \ LEQ J \ LEQ C $ Wir assoziieren $ 4 $ Elemente : $ 2V + 4J-K $ für $ 0 \ LEQ K \ LEQ 3 $ . So erstellen Sie den $ 2 $ Permutationen, die mit einer Klausel verknüpft sind, verwenden wir einfach einen Zyklus auf den zugehörigen Elementen. Das heißt, $$ P (c_j)= (2V + 4J-3, 2V + 4J-2, 2V + 4J-1, 2V + 4J) $$ ( Wir fügen $ 2 $ Instanz von $ P (C_J) $ an das Set, das wir eine Teilmenge finden möchten -Sum später.)

Betrachten Sie den Variablen $ I $ -th, $ x_i $ , und assoziieren Sie mit den Elementen $ 2I-1 $ und $ 2i $ von $ s_ {2V + 4C} $ . So erstellen Sie die Permutation $ P (x_i) $ von variablen $ x_i $ Swap einfach die zugehörigen Elemente (< Span-Klasse="Math-Container"> $ 2I-1 $ und $ 2i $ ) und multiplizieren Sie mit der Permutation jeder Klausel, in der sie in enthalten ist . Dann können Sie in der Zyklusnotation schreiben: $$ P (x_i)= (2i-1, 2i) \ prod_ {j | x_i \ in c_j} p (c_j) $$

Berücksichtigen Sie jetzt den MultiSet $ M $ Das ist die Vereinigung des $ P (x_i) $ und $ p (\ bar {x_i}) $ und zweimal jeweils $ p (c_j) $ .

Wir definieren die Ziel-Permutation $ T $ AS:

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

claim: Es gibt eine Subset $ x $ von $ M $ das komponiert mit der Ziel-Permutation $ T $ (lassen Sie mich $ P (x)= t $ schreiben) ) Wenn und nur wenn $ \ varphi $ erfüllt ist.

Angenommen, ein solcher $ x $ existiert, dann wissen wir $ x $ Enthält genau einen von $ p (x_i) $ und $ P (\ bar {x} _i) $ , wie es ist Der einzige Weg für die Zusammensetzung von $ x $ um den Zyklus $ (2i-1, 2i) $ . Darüber hinaus können wir sehen, dass für jede Klausel $ C_J \ in \ varphi $ , mindestens eine, wenn Variablen sie erfüllt, um $ P (C_J) ^ 3 $ in $ p (x) $ Wir müssen einen $ P (\ \ \ ell_i) $ so daß das wörtliche $ \ ell_i $ ist in $ c_j $ . Beachten Sie, dass die zwei Instanzen von $ P (C_J) $ in $ x $ nicht ausreicht. Daher gibt es eine Zuordnung von Variablen, die jede Klausel erfüllt. Seien Sie für die Rückwärtsrichtung $ \ Sigma $ eine erfüllende Zuordnung von $ \ varphi $ . Wenn $ \ Sigma (x_i)= 1 $ dann $ x $ enthalten, enthalten $ P (x_i) $ und ansonsten lassen wir sie $ p (\ bar {x} _i) $ enthalten. Für jede Klausel $ c_j $ wissen wir, dass zwischen $ 0 \ leq r_j \ leq 2 $ variablen auf vorhanden ist Es ist nicht zufrieden mit $ \ Sigma $ , und wir fügen $ r_j $ Ereignissen der $ p (c_j) $ bis $ x $ , so diese Weise $ P (x) $ enthält $ P (c_j) ^ 3 $ . Es ist klar, dass die Zusammensetzung von

Tainer "> $ x $ gleich $ t $ .

Answer 2

Das Problem der Subset-Summen ist noch schwieriger (NP-Hard) für spezielle Gruppen, die Sie in $ s_n $ einbetten können. Sehen Sie sich das Papier an, das Sie in der Problembeschreibung verknüpft haben.

$ \ textbf {Beobachtung:} $ $ g $ Kann als Kombination von Elementen < Span-Klasse="Math-Container"> $ \ {g_1, \ ldots, g_k \} $ , wenn und nur wenn $ g \ in \ langle g_1, \ ldots, G_K \ Rangle $ . Unter der Annahme, dass jeder von $ g_i $ eine beliebige Anzahl von Malen erscheint.

Die Komplexität des Problems hängt von der Eingabedarstellung ab. Es gibt zwei zwei am häufigsten verwendete Wege, Cayley-Tabelle und Generierungsset. Für Cayley-Tisch sehen Sie dieses Papier für Ergebnisse. Lesen Sie das CGM (Cayley-Mitgliedschaftsproblem) Link

$ \ textbf {cgm} $

$ \ textbf {Input:} $ Eine Gruppe $ G $ an seiner Cayley-Tabelle, < Span-Klasse="Math-Container"> $ x \ Subseteq G $ und $ t \ in G $ .

$ \ textbf {Ausgabe:} $ Hört $ t $ Zugehörigkeit zum Untergroup $ \ Langle X \ Rangle $ erzeugt von $ x $ ?

Im Allgemeinen ist das Problem in symmetrischem Protokollraum.

---

$ \ Langle A \ Rangle $ Untergruppe, die von $ A $

erzeugt wird