Gibt es ein P-vollständiges Problem bei diophantinischen Gleichungen?

11

Im Allgemeinen entspricht die Entscheidung, ob eine diophantinische Gleichung ganzzahlige Lösungen enthält, dem Stoppproblem. Ich glaube, dass die Entscheidung, ob eine quadratische Diophantin-Gleichung eine Lösung hat, NP-vollständig ist. Gibt es eine weitere Einschränkung der beteiligten Gleichungen, die ein P-vollständiges Problem ergibt?

cc.complexity-theory linear-algebra polynomials Jacob Edelman
quelle
1
Ich denke, ein Problem im Zusammenhang mit gcd wurde P vollständig gezeigt.
T ....
3
@ EmilJeřábek Ups, ich habe das Ergebnis falsch angegeben. Die Lösung muss in den positiven Begründungen liegen. Es ist als Problem A.4.2 in A Compendium of Problems Complete for P , a 1991 Tech, aufgeführt. Bericht von Greenlaw et al.
Mhum
2
@ EmilJeřábek Natürlich ist dies über die ganzen Zahlen nur eine ganzzahlige Programmierung. Was ich damit gemeint habe, ist, dass es etwas irreführend ist, lineare Programmierung wie ein diophantinisches Gleichungsproblem klingen zu lassen, indem man sagt, man wolle eine rationale Lösung, weil das Beharren auf einer rationalen Lösung dem Problem keine Einschränkung hinzufügt. Das heißt, wenn Sie fragen würden, ob das lineare Gleichungssystem eine Lösung über die nicht negativen Realzahlen hätte, wäre das Problem genau das gleiche.
Sasho Nikolov
1
@SashoNikolov Es ist keine Einschränkung. Ohne Angabe der Domäne für Lösungen ist das Problem einfach falsch , es sei denn, die Domäne kann aus dem Kontext abgeleitet werden. Und hier ist der Kontext so, dass die implizite Domäne die ganzen Zahlen sind, daher muss man explizit angeben, dass es sich um etwas anderes handelt. Ja, hier spielt es keine Rolle, ob man die Rationalen, Realen oder ein anderes Feld der Eigenschaft 0 auswählt. Mhums Wahl, es "rational" zu nennen, gilt ebenso wie Ihre Wahl, es "real" zu nennen.
Emil Jeřábek 3.0
1
@ EmilJeřábek Ich stimme größtenteils dem zu, was du sagst. Was ich irgendwie nicht vermitteln kann, ist, dass mir bei der linearen Programmierung der zahlentheoretische Aspekt des Problems der diophantinischen Gleichungen fehlt.
Sasho Nikolov

Antworten:

-3

Nein, soweit ich weiß, ist das Diaphantin-Problem im Allgemeinen unentscheidbar und entspricht somit dem Stopp-Problem. Wenn die Gleichungen auf quadratisch beschränkt sind, ist es np-vollständig, und die lineare Diaphantin-Gleichung kann auf ein ganzzahliges Programmierproblem und eine lineare Diophantin-Gleichung reduziert werden Gleichungen, integrale Lösungen existieren genau dann, wenn die GCD der Koeffizienten der beiden Variablen den konstanten Term perfekt teilt.

riemann77
quelle