Existe um problema de P completo nas equações diofantinas?

11

Em geral, decidir se uma equação diofantina tem soluções inteiras é equivalente ao problema de parada. Acredito que decidir se uma equação diofantina quadrática tem alguma solução é NP-completo. Existe alguma restrição adicional nas equações envolvidas que gera um problema de P completo?

cc.complexity-theory linear-algebra polynomials Jacob Edelman
fonte
1
Eu acho que um problema relacionado ao MDC foi mostrado P completo.
T ....
3
@ EmilJeřábek Ops, eu indevi o resultado. A solução deve estar nos racionais positivos . Ele está listado como problema A.4.2 em Um compêndio de problemas completo para P , uma tecnologia de 1991. Relatório de Greenlaw, et al.
Mhum 8/12
2
@ EmilJeřábek Obviamente, sobre os números inteiros, isso é apenas programação inteira. O que eu quis dizer é que fazer a programação linear soar como um problema do tipo equações diofantinas, dizendo que você quer uma solução racional, é um pouco enganador, porque insistir em uma solução racional não adiciona restrições ao problema. Ou seja, se você perguntasse se o sistema de equações lineares tinha uma solução sobre os reais não negativos, o problema seria exatamente o mesmo.
Sasho Nikolov 12/12
1
@SashoNikolov Não é uma restrição. Sem especificar o domínio para soluções, o problema é simplesmente mal formado , a menos que o domínio possa ser deduzido do contexto. E aqui o contexto é tal que o domínio implícito seria o número inteiro; portanto, é necessário declarar explicitamente que é algo diferente. Sim, aqui não importa se alguém escolhe os racionais, os reais ou qualquer outro campo da característica 0. A escolha de Mhum para chamá-lo de "racional" é igualmente válida como a sua escolha para chamá-lo de "real".
Emil Jeřábek 3.0 13/12
1
@ EmilJeřábek Eu concordo principalmente com o que você está dizendo. De alguma forma, estou deixando de transmitir que, para mim, a programação linear carece do aspecto teórico dos números do problema das equações diofantinas.
Sasho Nikolov

Respostas:

-3

Não, tanto quanto eu sei que o problema diaphantino em geral é indecidível, portanto, equivale a interromper o problema, se as equações forem restritas a serem quadráticas, então é np-complete, e a equação linear diaphanina pode ser reduzida ao problema de programação inteira e para a equação diofantina linear equações, existem soluções integrais se, e somente se, o MDC dos coeficientes das duas variáveis ​​divide perfeitamente o termo constante.

riemann77
fonte