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$

ds.algorithms complexity-classes reductions nt.number-theory np-complete
źródło

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

Odpowiedzi:

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