¿Resolver sistemas de ecuaciones módulo en para compuesto?

19

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 kmnk

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 clasesZ/kZ ". 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 ?

Niel de Beaudrap
fuente
enlace citeseerx para el borrador del documento . ps: una forma más robusta de tratar con modk es usar modkA donde A[k1] es el conjunto de recordatorios aceptados modk . También hay una pregunta relacionada en la complejidad de la prueba, cf. " The Proof Complexity of Linear Algebra " por Soltys y Cook, APAL 2004.
Kaveh
2
¿Qué pasa con solo k = 4 y paridad-L?
domotorp

Respuestas:

9

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:

Forma normal La clase coMod k L consta de idiomas L de la forma L  =  L p 1  ∩  L p 2  ∩ ... ∩  L p r  , donde L p j  ∈  coMod p L y donde p j se extiende sobre los factores primos de k .

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 L , se deduce que los sistemas de resolución de ecuaciones mod k figura en Comod k L . p t jpjejpjtj

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 ].

Niel de Beaudrap
fuente
Me gustaría saber, ¿es constante en su pregunta / respuesta? Estoy interesado en el caso donde el tamaño de no es ilimitado. kkk
Juan Bermejo Vega
1
@Juan: Sí, es una constante, aunque sea una constante. k
Niel de Beaudrap