К какому классу сложности относится эта проблема теории чисел?

«Если , существует ли , » является -полным. $a,b,c\in\Bbb N$ $x,y\in\Bbb N$ $ax^2+by=c$ $\mathsf{NP}$

К какому классу сложности относится «При условии , существуют ли , »? $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
источник

Почему первая проблема NP-завершена? Ссылка будет оценена. :)

Майкл Вехар

@MichaelWehar, Quadratic Diophantine является NP-полной. Я думаю, что это даже в Гари и Джонсона.

Каве

Это AN8 в Garey and Johnson, стр. 250: Manders and Adleman, «NP-полные задачи решения для бинарных квадратиков», 1978.

Каве

Существование рациональных решений полиномиально сводимо к факторингу, следовательно, в

: используя принцип Хассе , это сводится к проверке того, что символ Гильберта

для всех простых

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$

Эмиль Йержабек

a = b = 1

$a=b=1$

c

$c$

p \equiv 3 (\mod 4)

$p\equiv3\pmod4$

c

$c$

c

$c$

Ответы:

Добавлено позже: Как отмечено в комментариях, верхняя граница NP является тривиальной, если a, b и c положительны, как было задано.

Теорема 1.2 в этой статье показывает, что решение о том, имеет ли данное диофантово уравнение с двумя переменными решение, находится в NP.

Manu
источник

Я не считаю, что это хороший ответ (он говорит об очевидном).

Это, кажется, отвечает на вопрос, который был задан. Если вы намеревались предоставить дополнительные условия, вам необходимо включить их в вопрос.

Андрас Саламон,

@ AndrásSalamon, это не так, верхняя граница NP кажется тривиальной, когда и оба неотрицательны (так что и полиномиально ограничены в , и ). Реальный вопрос, если это трудно для NP.

a

$a$

b

$b$

x

$x$

y

$y$

a

$a$

b

$b$

c

$c$

Каве

@Kaveh: да, но это не то, что спросили. Кроме того, я предполагаю, что a, b, c заданы в двоичном виде, поэтому x и y ограничены только в n?

Андрас Саламон,

@ AndrásSalamon, их размер полиномиально ограничен по . Как я уже сказал, нахождение в NP тривиально для этой проблемы. В статье говорится о более общем случае, о котором вопрос не идет.

n

$n$

Каве