¿Hay un problema P-completo en las ecuaciones de diofantina?

11

En general, decidir si una ecuación de diofantina tiene alguna solución entera es equivalente al problema de detención. Creo que decidir si una ecuación de diofantina cuadrática tiene alguna solución es NP-completo. ¿Existe una restricción adicional en las ecuaciones involucradas que produce un problema P-completo?

cc.complexity-theory linear-algebra polynomials Jacob Edelman
fuente
1
Creo que un problema relacionado con gcd se mostró completo.
T ....
3
@ EmilJeřábek Vaya, he declarado mal el resultado. La solución debe estar en los racionales positivos . Está listado como el problema A.4.2 en A Compendium of Problems Complete for P , a Tech de 1991. Informe de Greenlaw, et al.
mhum
2
@ EmilJeřábek Por supuesto, sobre los enteros, esto es solo programación entera. Lo que quise decir es que hacer que la programación lineal suene como un problema del tipo de ecuaciones diofantinas al decir que quieres una solución racional es un poco engañoso porque insistir en una solución racional no agrega ninguna restricción al problema. Es decir, si preguntara si el sistema de ecuaciones lineales tenía una solución sobre los reales no negativos, el problema sería exactamente el mismo.
Sasho Nikolov
1
@SashoNikolov No es una restricción. Sin especificar el dominio para las soluciones, el problema simplemente está mal formado , a menos que el dominio pueda inferirse del contexto. Y aquí el contexto es tal que el dominio implícito serían los enteros, por lo tanto, uno necesita declarar explícitamente que es algo diferente. Sí, aquí no importa si uno elige los racionales, reales o cualquier otro campo de la característica 0. La elección de Mhum de llamarlo "racional" es igualmente válida que su elección de llamarlo "real".
Emil Jeřábek
1
@ EmilJeřábek Estoy de acuerdo con lo que dices. Lo que de alguna manera no puedo transmitir es que para mí la programación lineal carece del aspecto teórico numérico del problema de las ecuaciones de diofantina.
Sasho Nikolov

Respuestas:

-3

No, hasta donde yo sé, el problema de la diafantina en general es indecidible, por lo tanto equivalente al problema de detención, si las ecuaciones están restringidas a ser cuadráticas, entonces es np-completo, y la ecuación de diafantina lineal puede reducirse a un problema de programación entero y para la ecuación lineal de diofantina. ecuaciones, existen soluciones integrales si y solo si, el MCD de coeficientes de las dos variables divide el término constante perfectamente.

riemann77
fuente