A solução de sistemas de equações módulo em para composta?

19

Estou interessado na complexidade de resolver equações lineares módulo k , para k arbitrário (e com um interesse especial em potências primárias), especificamente:

Problema. Para um dado sistema de m equações lineares em n módulo desconhecido k , existem soluções?

No resumo de seu artigo Estrutura e importância das classes MOD do espaço de log nas classes Mod k L , Buntrock, Damm, Hertrampf e Meinel afirmam que " demonstram seu significado ao provar que todos os problemas padrão da álgebra linear sobre os anéis finitos Z/kZ estão completos para essas classes ". Em uma inspeção mais detalhada, a história é mais complicada. Por exemplo, Buntrock et al. mostra (por um esboço de prova em um rascunho anterior e de acesso livre encontrado por Kaveh, obrigado!) que resolver sistemas de equações lineares está na classe complementar coMod k L , pork prime. Não se sabe que essa classe é igual a Mod k L para k composto, mas não se preocupe com isso - o que me preocupa é o fato de eles não fazerem comentários sobre se a solução de sistemas de equações lineares mod k está contida em coMod k L para k composto!

Pergunta: A solução de sistemas de equações lineares no módulo k está contida no coMod k L para todos os k positivos?

Se você puder resolver sistemas de equações modulo com uma potência mais alta q de um primo p , poderá resolvê-los também com módulo p ; então resolver sistemas de equações modulo q é coMod p L -hard. Se você pudesse mostrar que esse problema está no Mod q L , você acabaria mostrando Mod k L  =  coMod k L para todos os k . É provável que seja difícil provar isso. Mas está em coMod k L ?

Niel de Beaudrap
fonte
link citeseerx para a redação do artigo . ps: uma maneira mais robusta de lidar com é usar que é o conjunto de lembretes aceitos . Há também uma questão relacionada à complexidade da prova, cf. " A complexidade da prova de álgebra linear " de Soltys e Cook, APAL 2004.modkmodkAUMA[k-1 1]modk
Kaveh
2
que tal apenas k = 4 e paridade-L?
domotorp

Respostas:

9

Estou feliz em dizer que eu penso que nós podemos responder a esta pergunta de forma afirmativa: isto é, decidir se uma congruência linear é viável modulo k é Comod k L -completo.

Na verdade, podemos reduzir esse problema ao caso especial das potências primárias. Pode-se mostrar que:

Forma Normal. A classe coMod k L consiste em idiomas L na forma L  =  L p 1  ∩  L p 2  ∩ ... ∩  L p r  , onde L p j  ∈  coMod p L e onde p j varia sobre os fatores primos de k .

Pelo Teorema dos Restantes, qualquer solução para um sistema de equações modula cada uma das potências primárias dividindokdá origem a uma solução para o mesmo sistema, modk. Portanto, se resolver sistemas de equações linearessobrep t jpjejpjtj está contido emComodpL, segue-se que os sistemas de resolução de equações modkestá contido emComodkG.

Existe um algoritmo padrão, descrito por McKenzie e Cook, para reduzir congruências lineares, um poder primordial na construção de um conjunto de abrangência para seu espaço nulo (ou seja, para A x  =  y em um determinado anel, construa uma base para o espaço nulo de [  A  |  y  ] e veja se existem soluções com um coeficiente final de -1); e subsequentemente para reduzir a construção de potências primárias do módulo de espaços nulos para a construção de potências primárias do módulo de espaços nulos e potências primárias do módulo de multiplicação de matrizes. As duas últimas tarefas são problemas viáveis ​​para o coMod k L , desde que você possa construir as matrizes envolvidas.

Acontece que as matrizes envolvidas na redução de McKenzie e Cook podem elas mesmas ser computadas por multiplicação de matrizes e (crucialmente) divisão por um fator constante. Felizmente, para potências primárias, os coeficientes das matrizes envolvidas podem ser computados na fita de trabalho usando um oráculo para as máquinas coMod p L ; e a divisão por uma constante pode ser realizada em CN 1 , que é de novo possível em Comod p L . Assim, verifica-se que todo o problema é em última análise factível em Comod k L .

Para detalhes completos, consulte [ arxiv: 1202.3949 ].

Niel de Beaudrap
fonte
Eu gostaria de saber, é constante em sua pergunta / resposta? Estou interessado no caso em que o tamanho de k não é ilimitado. kk
Juan Bermejo Vega
11
@ Juan: Sim, é uma constante, embora seja constante. k
Niel de Beaudrap