Considere el siguiente problema de prueba de membresía de subgrupo abelian .
Entradas:
Un grupo abeliano finito con arbitrariamente grande .
Un generador de conjunto de un subgrupo .
Un elemento .
Salida: 'sí' si y 'no' en otro lugar '.
Pregunta: ¿Se puede resolver este problema de manera eficiente en una computadora clásica? Considero un algoritmo eficiente si utiliza recursos de tiempo y memoria en el sentido habitual de las máquinas Turing clásicas. Tenga en cuenta que podemos asumir para cualquier subgrupo . El tamaño de entrada de este problema es .
Un poco de motivación . Intuitivamente, parece que el problema puede abordarse con algoritmos para resolver sistemas lineales de congruencias o ecuaciones lineales de diofantina (lea a continuación). Sin embargo, parece que hay diferentes nociones de eficiencia computacional utilizadas en el contexto de los cálculos con enteros, tales como: tiempo polinomial fuertemente versus débilmente, complejidad algebraica versus bit. No soy un experto en estas definiciones y no puedo encontrar una referencia que establezca claramente esta pregunta.
Actualización: la respuesta al problema es "sí".
En una respuesta tardía, propuse un método basado en las formas normales de Smith que es eficiente para cualquier grupo con la forma prescrita.
Una respuesta por shows Blondin que en el caso particular en que todo son de la forma d i = N e i i y N i , ae i son "pequeños números enteros" entonces el problema pertenece a NC 3 ⊂ P . Los enteros pequeños son exponencialmente pequeños con el tamaño de entrada: O ( log log | A | ) .
En mi respuesta usé "subgrupos ortogonales" para resolver este problema, pero creo que esto no es necesario. Intentaré proporcionar una respuesta más directa en el futuro basada en un método de formularios Echelon de fila que estoy leyendo.
Algunos enfoques posibles
El problema está estrechamente relacionado con la resolución de un sistema lineal de congruencias y / o ecuaciones lineales de diofantina. Resumo brevemente estas conexiones para completarlas.
Tome como la matriz cuyas columnas son los elementos del conjunto generador { h 1 , ... , h n } . El siguiente sistema de ecuaciones.
tiene una solución si y sólo si .
Si todos los factores cíclicos tienen la misma dimensión existe un algoritmo basado en las formas normales de Smith que resuelve el problema en tiempo polinómico. En este caso, un algoritmo eficiente de [1] encuentra la forma normal de Smith de : devuelve una matriz diagonal y dos matrices invertibles y modo que . Esto redujo el problema a la resolución del sistema de sistema equivalente con diagonal. Podemos decidir eficientemente si el sistema tiene una solución utilizando el algoritmo euclidiano.
El ejemplo anterior sugiere que el problema puede resolverse eficientemente utilizando técnicas similares en el caso general. Podemos intentar resolver el sistema haciendo operaciones modulares, o convirtiendo el sistema en un sistema más grande de ecuaciones lineales de diofantina. Algunas técnicas posibles para abordar el problema que se me ocurren son:
- Cálculo de las formas normales de Smith .
- Cálculo de la fila forma escalonada de .
- Eliminación gaussiana entera.
fuente
Respuestas:
Verificar si (donde son vectores de acuerdo con los comentarios del OP) es equivalente a verificar si hay una solución para este sistema:b∈⟨h1,…,hn⟩ hi
En su caso son números pequeños (es decir, su valor es logartímico en el tamaño de entrada). Desafortunadamente, no parece que podamos suponer que son pequeños.e1,…,eN d1,…,dn
Si lo son, puede encontrar una solución para el sistema en partir de un resultado de McKenzie & Cook [1] . Este artículo muestra que la resolución de congruencias lineales módulo un número entero con factores pequeños (LCON) está en . Además, este problema es equivalente al problema de pertenencia al grupo de permutación abeliana (AGM). La tesis doctoral de McKenzie está totalmente dedicada a esos problemas [1] . Más recientemente, esos problemas fueron considerados por Arvind y Vijayaraghavan [3] .NC3 NC3 NC1
[1] Pierre McKenzie y Stephen A. Cook. La complejidad paralela de los problemas del grupo de permutación abeliana. 1987.
[2] Pierre McKenzie. Complejidad paralela y grupos de permutación. 1984
[3] V. Arvind y TC Vijayaraghavan. Clasificación de problemas en congruencias lineales y grupos de permutación abeliana utilizando clases de recuento de espacios de registro. 2010
fuente
Después de un tiempo, logré encontrar un algoritmo quizás no óptimo pero simple que demuestra que la complejidad del problema es polinómica.
Existen algoritmos clásicos eficientes para los problemas (a) y (b) (ver análisis a continuación). Esto da una pertenencia-test eficiente desde un elemento es ortogonal a si y sólo si .b H⊥ h∈H
Análisis
El subgrupo ortogonal se define mediante el grupo de caracteres de como: Propiedades principales:H⊥ G
Algoritmo para (a) :
Sigo un algoritmo de [ 1 ] con pequeñas variaciones. pertenece a si y solo si para todo , pero, por linealidad, es suficiente para mostrar para cada generador de . Expandiendo el carácter en términos de exponenciales (aquí implícitamente uso la descomposición del factor cíclico) esta condición es equivalente a Para resolver estas ecuaciones, calcule usando el algoritmo euclidiano y los númerosg H⊥ χg(h)=1 h∈H χb(hi)=1 H
Algoritmo para (b) :
Como ya sabemos cómo calcular un generador de conjunto de , es fácil comprobar si un elemento dado pertenece a . Primero calcule un conjunto generador de . Entonces, por definición, pertenece a si y solo si para todos los generadores de . Dado que hay un número O (polylog ( )) de ellos y esto se puede hacer de manera eficiente utilizando la aritmética modular que hemos terminado. b H ⟨ g 1 , ... , g s ⟩ H ⊥ b H χ b ( g i ) = 1 H ⊥ | G |H⊥ b H ⟨g1,…,gs⟩ H⊥ b H χb(gi)=1 H⊥ |G|
fuente