Complejidad del problema de intersección de coset

17

Dado el grupo de simetría y dos subgrupos y , ¿se mantiene ? G , H S n π S n G π H = Snortesol,HSnorteπSnortesolπH=

Hasta donde yo sé, el problema se conoce como el problema de intersección de coset. Me pregunto cuál es la complejidad. En particular, ¿se sabe que este problema está en coAM?

Además, si se limita a ser abeliano, ¿en qué se convierte la complejidad?H

maomao
fuente
2
¿Cómo se representan los dos grupos como entrada?
Emil Jeřábek apoya a Monica el
1
por convención, son dados por conjuntos de generadores.
maomao
1
El problema de la intersección de coset generalmente se formula de manera opuesta: la respuesta es sí si se intersectan. Es esta versión del problema que está en . nortePAGCoUNMETRO
Joshua Grochow
Una nota al margen interesante, que no invalida nada de lo anterior: el isomorfismo gráfico, la intersección de coset y el isomorfismo de cuerdas fueron el tema de un nuevo resultado descrito por Babai por primera vez en un seminario hace un par de días. Todavía no hay publicación, pero parece que ahora hay un algoritmo cuasi-polinomial para todos ellos.
Perry

Respuestas:

11

Tiempo moderadamente exponencial y (para lo opuesto al problema como se indica: la intersección de Coset generalmente se considera que tiene una respuesta "sí" si las cosets se cruzan, opuesto a cómo se indica en el OQ).CoUNMETRO

Luks 1999 ( copia del autor libre ) dio un algoritmo de veces, mientras que Babai (ver su tesis de doctorado de 1983, también Babai-Kantor-Luks FOCS 1983 , y una versión de revista que aparecerá) dio un 2 ˜ O ( 2O(n)algoritmo de tiempo, que sigue siendo el más conocido hasta la fecha. Desde isomorfismo gráfico se reduce a intersección clase lateral-cuadrática tamaño, la mejora de este a2 ~ O (n 1 / 4 - ε )mejoraría el estado de la técnica para isomorfismo gráfico.2O~(n)2O~(n1/4ϵ)

Joshua Grochow
fuente
9

Considere el complemento, es decir, dónde se le pide que pruebe si . Como he señalado en esta respuesta , probando si g g 1 , ... , g k es decir en NC P [1]. Entonces puedes adivinar g , h S n y probar en tiempo polinómico si g G , h H y g π = h . Esto produce un NPsolπHsolsol1,...,solkCAROLINA DEL NORTEPAGsol,hSnortesolsolhHsolπ=hnotario públicolímite superior y, por lo tanto, su problema está en .coNP

Editar : se muestra en [2, Thm. 15] que el problema de intersección de coset está en . Como se señaló aquí , p. 7, el problema de intersección de coset no es NP-completo, a menos que la jerarquía de tiempo polinómica se colapse. Además, se observa aquí , p. 6, que Luks demostró que el problema está en P cuando H es solucionable, lo que incluye el caso de H abelian.notario públicovagabundoPAGHH

[1]  L. Babai, EM Luks y A. Seress. Grupos de permutación en Carolina del Norte . Proc. XIX simposio anual de ACM sobre teoría de la informática, pp. 409-420, 1987.

[2] L. Babai, S. Moran. Juegos Arthur-Merlin: un sistema de pruebas aleatorias y una jerarquía de clases de complejidad . Revista de Informática y Ciencias del Sistema, vol. 36, número 2, págs. 254-276, 1988.

Michael Blondin
fuente
Muchas gracias por la respuesta. Para el caso H es un subgrupo normal, está claro. Sin embargo, si H es simplemente abeliano, no está realmente claro para mí. ¿ todavía se mantiene? (Perdón por mi estupidez ...)solH= <st:sS,tT>
maomao
Mi mal, mi cerebro mezcló "normal" y "solucionable" por un momento. Lo siento. Edité la respuesta, espero que responda tu pregunta.
Michael Blondin
1
Cuando H es un subgrupo normal de G, el problema de intersección de coset es mucho más fácil: se reduce solo al problema de membresía (es en G). π
Joshua Grochow
Bien, gracias Esa parte de mi respuesta es bastante inútil entonces.
Michael Blondin
Eliminé el párrafo, era confuso.
Michael Blondin