Problema della somma del sottoinsieme per le permutazioni

Question

Dato permutazioni $ G_1, \, \ LDOTS, G_M \ IN S_N $ di Dimensione $ N $ e permutazione target $ G \ in s_n $ , decidere se esiste un sottoinsieme di $ \ {G_1, \, \ LDOTS, G_M \} $ , quale composizione in qualche ordine (o, in alternativa, come variante di questo problema, nello stesso ordine) è uguale a $ G $ < / span>, cioè $ G_ {i_1} \ Circ g_ {i_2} \ Circ \ clotty \ Circ g_ {i_k}= G $ .

Questo è in realtà un subset somma problema , ma per gruppo simmetrico $ (s_n, \ circling) $ invece di < span class="math-container"> $ (\ mathbb {z}, +) $ .

Le domande sono:

.
1. C'è una soluzione nota in tempo polinomiale?
2. Altrimenti, è questo problema noto come NP-Complete?

Ho trovato un documento su problemi di zaino in gruppi , tuttavia, questi risultati sembrano essere Non applicabile per il gruppo simmetrico.

Answer 1

Questo problema, che chiamerò sottoinsieme-somm-somma, è np-completo. L'iscrizione è facile: indovina il sottoinsieme non deterministicamente e quindi controllare.

Per la durezza si può ridurre da 3CNF-SAT in modo molto simile alla prova standard della durezza per la somma del sottoinsieme.

Let $ \ Varfi $ Sii una formula di input con $ v $ variabili e $ c $ clausole. Costruiremo un'istanza di sottoinsieme-somm-somma su $ s_ {2v + 4c} $ . Per ogni variabile che costruiamo $ 2 $ permutazioni (una che rappresenterà la variabile e una che rappresenterà la sua negazione), e per ogni clausola costruiremo $ 2 $ Permutazioni pure.

a ciascuna clausola $ c_j, 1 \ leq j \ leq c $ associato $ 4 $ elementi : $ 2v + 4J-k $ per $ 0 \ leq k \ leq 3 $ . Per costruire la $ 2 $ Permutazioni associate a una clausola che facciamo semplicemente un ciclo sui suoi elementi associati. Cioè, $$ P (c_j)= (2V + 4J-3, 2V + 4J-2, 2V + 4J-1, 2V + 4J) $$ ( Aggiungeremo $ 2 $ istanza di $ p (c_j) $ al set che vogliamo trovare un sottoinsieme -so in seguito.)

Considerare la $ i $ -th variabile, $ x_i $ , e associa ad esso gli elementi $ 2i-1 $ e $ 2i $ di $ s_ {2V + 4C} $ . Per costruire la permutazione $ p (x_i) $ di variabile $ x_i $ semplicemente scambia i suoi elementi associati (< Span Class="Math-Container"> $ 2i-1 $ e $ 2i $ ), e moltiplicare per la permuta di ciascuna clausola è contenuto in . Quindi, nella notazione del ciclo che puoi scrivere: $$ P (x_i)= (2i-1, 2i) \ PROD_ {J | x_i \ in c_j} p (c_j) $$

Considera ora il multiset $ m $ Questa è l'unione della $ P (x_i) $ e $ P (\ bar {x_i}) $ e due volte ogni $ p (c_j) $ .

Definiamo il permutazione target $ T $ AS:

$$ T=PROD_ {I= 1} ^ V (2i-1, 2I) \ Cdot \ PROD_ {J= 1} ^ c P (c_j) ^ 3 $$

Reclamazione: Esiste un sottoinsieme $ x $ di $ m $ che componi al permutazione target $ t $ (lasciatemi scrivere $ P (x)= t $ ) Se e solo se $ \ VARPHI $ è soddisfavole.

Assume una tale classe $ x $ esiste, quindi conosciamo $ x $ contiene esattamente uno fuori da $ P (x_i) $ e $ P (\ bar {x} _i) $ , così com'è l'unico modo per la composizione di $ x $ per includere il ciclo $ (2i-1, 2i) $ . Inoltre, possiamo vederlo per ogni clausola $ c_j \ in \ Varfi $ , almeno una se le variabili soddisfanolo, da avere $ p (c_j) ^ 3 $ in $ P (x) $ Dobbiamo includere una $ P (\ ell_i) $ in modo tale che letterale $ \ ell_i $ è in $ c_j $ . Si noti che prendendo le due istanze di $ P (c_j) $ in $ x $ non è abbastanza. Pertanto, c'è un assegnazione di variabili che soddisfano ogni clausola. Per la direzione all'indietro, let $ \ sigma $ essere un assegnazione soddisfacente di $ \ varphi $ . Se $ \ Sigma (x_i)= 1 $ Quindi lasciamo $ x $ contenere $ P (x_i) $ e altrimenti lo lasciamo contenere $ p (\ bar {x} _i) $ . Per ogni clausola $ c_j $ , sappiamo che ci sono tra $ 0 \ Leq R_J \ Leq 2 $ Variabili su Non è soddisfatto da $ \ sigma $ , e aggiungiamo $ r_j $ occorrenze di $ P (c_j) $ a $ x $ , quindi in questo modo $ P (x) $ Include $ P (c_j) ^ 3 $ . È chiaro che la composizione di

tainer "> $ x $ uguale a $ T $ .

Answer 2

Il problema della somma del sottoinsieme è ancora più difficile (NP-Hard) per gruppi speciali che è possibile incorporare in $ s_n $ . Vedi la carta che hai collegato nella descrizione del problema.

$ \ textbf {osservazione:} $ $ G $ può essere grittens come combinazione di elementi < Span Class="Math-Container"> $ \ {G_1, \ LDOTS, G_K \} $ Se e solo se $ G \ in \ Langle G_1, \ Ldots, G_K \ Rangle $ . Sotto il presupposto che ciascuno di $ G_i $ può appare un numero qualsiasi di volte.

La complessità del problema dipende dalla rappresentazione di input. Ci sono due due modi più comunemente usati, tavolino Cayley e set di generazione. Per il tavolo Cayley Vedi questo documento per i risultati. Leggi il CGM (Problema di appartenenza a Cayley) Link

$ \ textbf {cgm} $

$ \ textbf {ingresso:} $ un gruppo $ G $ Dalla sua tavola Cayley, < Span Class="Math-Container"> $ x \ SOTETEQ G $ e $ T \ in G $ .

$ \ textbf {output:} $ fa $ T $ appartengono alla sottogruppi $ \ Langle x \ Rangle $ generato da $ x $ ?

In un problema generale è nello spazio del registro simmetrico.

---

.

$ \ Langle A \ Rangle $ significa sottogruppo generato da $ a $