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

'Gegeben , gibt es , ' ist -vollständig. $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by=c$ $\mathsf{NP}$

Zu welcher Komplexitätsklasse gehört 'Gegeben , gibt es , '? $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by^2=c$

ds.algorithms complexity-classes reductions nt.number-theory np-complete
quelle

Warum ist das erste Problem NP-vollständig? Eine Referenz wäre willkommen. :)

Michael Wehar

@MichaelWehar, Quadratisches Diophantin ist NP-vollständig. Ich denke es liegt sogar an Gary und Johnson.

Kaveh,

Es ist AN8 in Garey und Johnson, Seite 250: Manders und Adleman, "NP-vollständige Entscheidungsprobleme für binäre Quadrate", 1978.

Kaveh,

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

das Hilbert-Symbol

N P \cap c o N P

$\mathrm{NP}\cap\mathrm{coNP}$

(a / c, b / c)_{p} = 1

$(a/c,b/c)_p=1$

p ∣ 2 a b c

$p\mid2abc$

Emil Jeřábek unterstützt Monica

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

eine Summe von zwei Quadraten ist) wird gefragt, ob alle Primzahlen

a = b = 1

$a=b=1$

c

$c$

treten inmit gerader Vielheit auf, und meines Wissens ist es nicht bekannt, wie man dies effizienter testet alsfaktorisieren; vgl. mathoverflow.net/q/57981.

p \equiv 3 (\mod 4)

$p\equiv3\pmod4$

c

$c$

c

$c$

Emil Jeřábek unterstützt Monica

Antworten:

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

Ich weiß nicht, das ist eine gute Antwort (es heißt das Offensichtliche).

Dies scheint die gestellte Frage zu beantworten. Wenn Sie weitere Bedingungen beabsichtigen, müssen Sie diese in die Frage aufnehmen.

András Salamon

@ AndrásSalamon, die NP-Obergrenze scheint trivial zu sein, wenn

und

nichtnegativ sind (also sind

und

durch

und

polynomiell begrenzt ). Die eigentliche Frage ist, ob es für NP schwierig ist.

a

$a$

b

$b$

x

$x$

y

$y$

a

$a$

b

$b$

c

$c$

Kaveh

@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

@ 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

$n$

Kaveh