Problema de suma de subconjuntos para permutaciones

Question

Permutaciones dadas $g_1,\,\ldots, g_m \en S_n$ de tamaño $n$ y permutación de objetivos $g \en S_n$, decide si existe un subconjunto de $\{g_1,\, \ldots, g_m\}$, cuya composición en algún orden (o, alternativamente, como variante de este problema, en el mismo orden) es igual a $g$, es decir. $g_{i_1} \circ g_{i_2} \circ \cdots \circ g_{i_k} = g$.

Esto es en realidad un problema de suma de subconjuntos, pero para grupo simétrico $(S_n,\circ)$ en lugar de $(\mathbb{Z}, +)$.

Las preguntas son:

1. ¿Existe una solución conocida en tiempo polinomial?
2. De lo contrario, ¿este problema se conoce como NP-completo?

Encontré un documento sobre problemas de mochila en grupos, Sin embargo, estos resultados parecen no ser aplicables al grupo simétrico.

Answer 1

Este problema, que llamaré el subsecable-Perm-Sum, es NP-Completa. La membresía es fácil: adivina el subconjunto no determinista determinista y luego verifique.

Por dureza Se puede reducir de 3CNF-SAT de una manera muy similar a la prueba estándar de dureza para la suma de subsecre.

Let $ \ varphi $ Sé una fórmula de entrada con $ v $ variables y $ C $ cláusulas. Construiremos una instancia de subconjunto-sum-suma sobre $ s_ {2v + 4c} $ . Por cada variable que construimos $ 2 $ permutaciones (uno que representará la variable y uno que representará su negación), y para cada cláusula construiremos $ 2 $ Permutaciones también.

a cada cláusula $ c_j, 1 \ leq j \ leq c $ Nos asociamos $ 4 $ elementos : $ 2v + 4j-k $ para $ 0 \ leq k \ leq 3 $ . Para construir el $ 2 $ permutaciones asociadas a una cláusula Simplemente hagamos un ciclo en sus elementos asociados. Es decir, $$ P (C_J)= (2V + 4J-3, 2V + 4J-2, 2V + 4J-1, 2V + 4J) $$ ( Añadiremos $ 2 $ instancia de $ P (c_j) $ al conjunto que queremos encontrar un subconjunto -Sum más tarde.)

Considere el $ i $ -th variable, $ x_i $ y asociado con él los elementos $ 2i-1 $ y $ 2i $ de $ s_ {2v + 4c} $ . Para construir la permutación $ P (x_i) $ de la variable $ x_i $ simplemente cambie sus elementos asociados (< span class="Math-contenedor"> $ 2i-1 $ y $ 2i $ ), y multiplique por la permutación de cada cláusula que está contenida en . Luego, en la notación del ciclo, puede escribir: $$ P (x_i)= (2i-1, 2i) \ PROD_ {J | x_i \ en c_j} p (c_j) $$

Considere ahora el multiset $ m $ que es la unión del $ P (x_i) $ y $ P (\ bar {x_i}) $ y dos veces cada uno $ P (c_j) $ .

Definimos la permutación de destino $ t $ como:

$$ t=prod_ {i= 1} ^ v (2i-1, 2i) \ CDOT \ PROD_ {J= 1} ^ C P (C_J) ^ 3 $$

reclamación: hay un subconjunto $ x $ de $ m $ que se compone de la permutación objetivo $ t $ (déjame escribir $ p (x)= t $ ) Si y solo si $ \ varphi $ es satisfactorio.

Supongamos que un contenedor de matemáticas "> $ x $ existe, entonces conocemos $ x $ contiene exactamente uno de $ P (x_i) $ y $ P (\ bar {x} _i) $ , como es la única forma de que la composición de $ x $ incluirá el ciclo $ (2i-1, 2i) $ . Además, podemos ver que para cada cláusula $ c_j \ in \ varphi $ , al menos una si las variables lo satisfacen, como para tener $ P (c_j) ^ 3 $ en $ P (x) $ Tenemos que haber incluido un $ P (\ ELL_I) $ de tal que literal $ \ ell_i $ está en $ c_j $ . Tenga en cuenta que tomar las dos instancias de $ P (c_j) $ en $ x $ no es suficiente. Por lo tanto, hay una asignación de variables que satisface cada cláusula. Para la dirección atrasada, permita que $ \ sigma $ sea una asignación satisfactoria de $ \ varphi $ . Si $ \ sigma (x_i)= 1 $ luego dejamos $ x $ contienen $ P (x_i) $ y, de lo contrario, lo dejamos contener $ P (\ bar {x} _i) $ . Para cada cláusula $ c_j $ , sabemos que hay entre $ 0 \ \ leq r_j \ leq 2 $ variables en Eso no está satisfecho con $ \ sigma $ , y agregamos $ r_j $ ocurrencias de $ P (c_j) $ a $ x $ , de esta manera $ P (x) $ incluye $ P (c_j) ^ 3 $ . Está claro que la composición de

Tiner "> $ x $ es igual a $ t $ .

Answer 2

El problema de la suma de subconjuntos es aún más difícil (NP-difícil) para grupos especiales en los que puede integrarse $S_n$.Vea el documento que ha vinculado en la descripción del problema.

$ extbf{Observación:}$ $g$ se puede escribir como combinación de elementos $\{g_1,\ldots,g_k\}$ si y solo si $g \en \langle g_1,\ldots,g_k angle$.Bajo el supuesto de que cada uno de $g_i$ puede aparecer cualquier número de veces.

La complejidad del problema depende de la representación de entrada.Hay dos formas más utilizadas: la mesa Cayley y el grupo electrógeno.Para la tabla de Cayley, consulte este documento para obtener resultados.Lea el CGM (problema de membresía de Cayley) Enlace

$ extbf{MCG} $

$ extbf{Entrada :}$ Un grupo $g$ por su mesa Cayley, $X \subseteq G$ y $t \en G$.

$ extbf{Salida :}$ Hace $t$ pertenecer al subgrupo $\langle X angle$ generado por $X$?

En general, el problema está en el espacio logarítmico simétrico.

---

$\langle A angle$ significa subgrupo generado por $A$