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 equações lineares em módulo desconhecido , 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 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 ?
fonte
Respostas:
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:
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 jpejj ptjj está contido emComodpj L, 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 ].
fonte