Zu welcher Komplexitätsklasse gehört dieses Problem der Zahlentheorie?

12

'Gegeben , gibt es , ' ist -vollständig.ein,b,cNx,yNeinx2+by=cNP

Zu welcher Komplexitätsklasse gehört 'Gegeben , gibt es , '?ein,b,cNx,yNeinx2+by2=c


quelle
2
Warum ist das erste Problem NP-vollständig? Eine Referenz wäre willkommen. :)
Michael Wehar
2
@MichaelWehar, Quadratisches Diophantin ist NP-vollständig. Ich denke es liegt sogar an Gary und Johnson.
Kaveh,
2
Es ist AN8 in Garey und Johnson, Seite 250: Manders und Adleman, "NP-vollständige Entscheidungsprobleme für binäre Quadrate", 1978.
Kaveh,
4
Die Existenz rationaler Lösungen lässt sich polynomiell auf die Faktorisierung reduzieren, daher läuft es in nach dem Hasse-Prinzip für alle Primzahlen p das Hilbert-Symbol ( a / c , b / c ) p = 1 gilt 2 a b c . NPcoNP (a/c,b/c)p=1p2abc
Emil Jeřábek unterstützt Monica
5
Beachten Sie, dass es unwahrscheinlich ist, dass Sie (entweder für die ganzzahlige oder für die rationale Lösbarkeit) etwas Besseres als das Faktorisieren erhalten: Bereits im Sonderfall (dh ob c eine Summe von zwei Quadraten ist) wird gefragt, ob alle Primzahlen p 3 sindein=b=1c treten inmit gerader Vielheit auf, und meines Wissens ist es nicht bekannt, wie man dies effizienter testet alsfaktorisieren; vgl. mathoverflow.net/q/57981. p3(mod4)ccc
Emil Jeřábek unterstützt Monica

Antworten:

5

Später hinzugefügt: Wie in den Kommentaren erwähnt, ist die NP-Obergrenze trivial, wenn a, b und c positiv sind, wie angefragt wurde.

Satz 1.2 in dieser Arbeit zeigt, dass die Entscheidung, ob eine gegebene Diophantingleichung in zwei Variablen eine Lösung hat, in NP liegt.

Manu
quelle
3
Ich weiß nicht, das ist eine gute Antwort (es heißt das Offensichtliche).
2
Dies scheint die gestellte Frage zu beantworten. Wenn Sie weitere Bedingungen beabsichtigen, müssen Sie diese in die Frage aufnehmen.
András Salamon
4
@ AndrásSalamon, die NP-Obergrenze scheint trivial zu sein, wenn und b nichtnegativ sind (also sind x und y durch a , b und c polynomiell begrenzt ). Die eigentliche Frage ist, ob es für NP schwierig ist. abxyeinbc
Kaveh
1
@Kaveh: ja, aber das wurde nicht gefragt. Weiter nehme ich an, dass a, b, c binär gegeben sind, so dass x und y in n nur exponentiell begrenzt sind.
András Salamon
4
@ AndrásSalamon, Ihre Größe ist in polynomial begrenzt . Wie ich sagte, ist es für das Problem trivial, in NP zu sein. Das Papier handelt von einem allgemeineren Fall, um den es in der Frage nicht geht. n
Kaveh