À quelle classe de complexité ce problème de théorie des nombres appartient-il?

'Étant donné $a,b,c\in\Bbb N$ , y a-t-il $x,y\in\Bbb N$ , $ax^2+by=c$ ' est $\mathsf{NP}$ -complet.

À quelle classe de complexité «Étant donné $a,b,c\in\Bbb N$ , y a-t-il $x,y\in\Bbb N$ , $ax^2+by^2=c$ »?

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

Pourquoi le premier problème NP-complet? Une référence serait appréciée. :)

Michael Wehar

@MichaelWehar, Quadratic Diophantine est NP-complet. Je pense que c'est même dans Gary et Johnson.

Kaveh

C'est AN8 dans Garey et Johnson, page 250: Manders et Adleman, "NP-complete decision problems for binary quadratics", 1978.

Kaveh

L'existence de solutions rationnelles est polynomialement réductible à la factorisation, donc dans

: en utilisant le principe de Hasse , cela revient à vérifier que le symbole de Hilbert

pour tous les nombres premiers

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

Notez que (pour la solvabilité entière ou rationnelle) il est peu probable que vous obteniez quelque chose de mieux que la factorisation: déjà le cas spécial

(c'est-à-dire, si

est une somme de deux carrés) demande si tous les nombres premiers se produire en avec même multiplicité, et à ma connaissance, on ne sait pas comment tester cela plus efficacement que l'affacturage ; cf. 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

Réponses:

Ajouté plus tard: Comme indiqué dans les commentaires, la borne supérieure NP est triviale si a, b et c sont positifs, comme cela a été demandé.

Le théorème 1.2 de cet article montre que décider si une équation diophantienne donnée à deux variables a une solution est en NP.

Manu
la source

Je ne pense pas que ce soit une bonne réponse (cela indique l'évidence).

Cela semble répondre à la question posée. Si vous envisagez d'autres conditions, vous devez les inclure dans la question.

András Salamon

@ AndrásSalamon, ce n'est pas le cas, la borne supérieure NP semble triviale lorsque et sont tous deux non négatifs (donc et sont liés polynomialement par dans , et ). La vraie question est de savoir si c'est difficile pour NP.

a

$a$

b

$b$

x

$x$

y

$y$

a

$a$

b

$b$

c

$c$

Kaveh

@Kaveh: oui, mais ce n'est pas ce qui a été demandé. De plus, je suppose que a, b, c sont donnés en binaire, donc x et y ne sont liés exponentiellement que dans n?

András Salamon

@ AndrásSalamon, Leur taille est polynomiale bornée en . Comme je l'ai dit, être en NP est trivial pour le problème. Le document parle d'un cas plus général dont la question n'est pas.

n

$n$

Kaveh