Do jakiej klasy złożoności należy ten problem teorii liczb?

'Biorąc pod uwagę , czy jest , ' jest -kompletny. $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by=c$ $\mathsf{NP}$

Do której klasy złożoności należy „Biorąc pod uwagę , czy istnieje , '? $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by^2=c$

Dlaczego pierwszy problem NP-zupełny? Referencje będą mile widziane. :)

— Michael Wehar,

@MichaelWehar, Quadratic Diophantine jest NP-kompletny. Myślę, że nawet u Gary'ego i Johnsona.

— Kaveh

Jest to AN8 w Garey and Johnson, strona 250: Manders and Adleman, „NP-zupełne problemy decyzyjne dla binarnych kwadratów”, 1978.

— Kaveh

Istnienie racjonalnych rozwiązań sprowadza się wielomianowo do faktoringu, stąd w : przy użyciu zasady Hassego sprowadza się to do sprawdzenia, czy symbol Hilberta dla wszystkich liczb pierwszych .

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

Zauważ, że (dla liczb całkowitych lub racjonalnych) nie jest prawdopodobne uzyskanie czegoś lepszego niż faktoring: już w specjalnym przypadku (tj. Czy jest sumą dwóch kwadratów) pyta, czy wszystkie liczby pierwsze występują w nawet z mnóstwem, i zgodnie z moją najlepszą wiedzą, nie wiadomo jak przetestować to bardziej efektywnie niż faktoring ; por. mathoverflow.net/q/57981 .

a = b = 1

$a=b=1$

c

$c$

p \equiv 3 (\mod 4)

$p\equiv3\pmod4$

c

$c$

c

$c$

— Emil Jeřábek

Dodane później: Jak zauważono w komentarzach, górna granica NP jest trywialna, jeśli a, b i c są dodatnie, jak zostało to poproszone.

Twierdzenie 1.2 w tym artykule pokazuje, że decydowanie, czy dane równanie diofantyczne w dwóch zmiennych ma rozwiązanie, należy do NP.

— Manu
źródło

Nie twierdzę, że to dobra odpowiedź (stwierdza oczywistość).

To wydaje się odpowiadać na zadane pytanie. Jeśli zamierzasz spełnić dodatkowe warunki, musisz uwzględnić je w pytaniu.

— András Salamon,

@ AndrásSalamon, tak nie jest, górna granica NP wydaje się trywialna, gdy i są nieujemne (więc i są wielomianowo ograniczone przez , i ). Prawdziwe pytanie brzmi, czy jest to trudne dla NP.

a

$a$

b

$b$

x

$x$

y

$y$

a

$a$

b

$b$

c

$c$

— Kaveh

@Kaveh: tak, ale nie o to pytano. Ponadto zakładam, że a, b, c podano w postaci binarnej, więc xiy są ograniczone wykładniczo w n?

— András Salamon,

@ AndrásSalamon, Ich rozmiar jest wielomianowo ograniczony w . Jak powiedziałem, bycie w NP jest banalne dla problemu. Artykuł mówi o bardziej ogólnym przypadku, o którym nie chodzi w pytaniu.

n

$n$

— Kaveh