Estoy interesado en la complejidad de resolver ecuaciones lineales módulo k , para k arbitrario (y con un interés especial en las potencias primarias), específicamente:
Problema. Para un sistema dado de ecuaciones lineales en incógnitas módulo , ¿existe alguna solución?n k
En el resumen de su artículo Estructura e importancia de las clases MOD de espacio de registro en las clases Mod k L , Buntrock, Damm, Hertrampf y Meinel afirman que " demuestran su importancia al demostrar que todos los problemas estándar de álgebra lineal sobre los anillos finitos están completos para estas clases ". En una inspección más cercana, la historia es más complicada. Por ejemplo, Buntrock et al. demuestre (mediante un boceto de prueba en un borrador anterior y de libre acceso encontrado por Kaveh, ¡gracias!) que la solución de sistemas de ecuaciones lineales se encuentra en su lugar en la clase complementaria coMod k L , para kprincipal. No se sabe que esta clase sea igual a Mod k L para k compuesto, pero no importa eso, lo que me preocupa es el hecho de que no hacen ningún comentario sobre si la resolución de sistemas de ecuaciones lineales mod k está contenida en coMod k L para k compuesto!
Pregunta: ¿La solución de sistemas de ecuaciones lineales módulo k está contenida en coMod k L para todos los k positivos?
Si puede resolver sistemas de ecuaciones de módulo de mayor potencia q de un primo p , también puede resolverlos módulo p ; entonces resolver sistemas de ecuaciones módulo q es coMod p L -hard. Si pudieras demostrar que este problema está en Mod q L , terminarías mostrando Mod k L = coMod k L para todos los k . Es probable que sea difícil de probar. ¿Pero está en coMod k L ?
fuente
Respuestas:
Me complace decir que creo que podemos responder afirmativamente a esta pregunta: es decir, decidir si una congruencia lineal es factible módulo k es coMod k L -completo.
De hecho, podemos reducir este problema al caso especial de las potencias principales. Uno puede mostrar que:
Según el Teorema restante, cualquier solución a un sistema de ecuaciones módulo a cada una de las potencias primarias dividiendo k da lugar a una solución para el mismo sistema, mod k . Así que si la resolución de sistemas de ecuaciones lineales sobre está contenida en Comod p j L , se deduce que los sistemas de resolución de ecuaciones mod k figura en Comod k L . p t jpejj ptjj
Hay un algoritmo estándar, descrito por McKenzie y Cook para reducir las congruencias lineales módulo de una potencia principal para construir un conjunto de expansión para su espacio nulo (es decir, para A x = y sobre un anillo dado, construir una base para el espacio nulo de [ A | y ] y vea si existen soluciones con un coeficiente final de −1); y posteriormente para reducir la construcción de poderes primos de módulo de espacios nulos para construir primos de módulo de espacios nulos, y potencias de módulo de multiplicación de matriz. Ambas tareas son problemas que son factibles para coMod k L , siempre que pueda construir las matrices involucradas.
Resulta que las matrices involucradas en la reducción de McKenzie y Cook pueden calcularse por multiplicación matricial y (crucialmente) por un factor constante. Afortunadamente, para las potencias principales, los coeficientes de las matrices involucradas pueden calcularse en la cinta de trabajo utilizando un oráculo para máquinas CoMod p L ; y la división por una constante se puede realizar en NC 1 , que es de nuevo posible en Comod p L . Así que resulta que todo el problema es en última instancia factible en Comod k L .
Para detalles completos, ver [ arxiv: 1202.3949 ].
fuente